TheInfoList

OR:

Logic programming is a
programming paradigm Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms. Some paradigms are concerned mainly with implications for the execution model of the language, su ...
which is largely based on 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 prem ...
. Any program written in a logic
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 programmin ...
is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include
Prolog Prolog is a logic programming language associated with artificial intelligence and computational linguistics. Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primaril ...
, answer set programming (ASP) and
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 ...
. In all of these languages, rules are written in the form of ''
clauses In language, a clause is a constituent that comprises a semantic predicand (expressed or not) and a semantic predicate. A typical clause consists of a subject and a syntactic predicate, the latter typically a verb phrase composed of a verb wi ...
'': :H :- B1, …, Bn. and are read declaratively as logical implications: :H if B1 and … and Bn. H is called the ''head'' of the rule and B1, ..., Bn is called the ''body''. Facts are rules that have no body, and are written in the simplified form: :H. In the simplest case in which H, B1, ..., Bn are all
atomic formula In mathematical logic, an atomic formula (also known as an atom or a prime formula) is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subfor ...
e, these clauses are called definite clauses or Horn clauses. However, there are many extensions of this simple case, the most important one being the case in which conditions in the body of a clause can also be negations of atomic formulas. Logic programming languages that include this extension have the knowledge representation capabilities of a
non-monotonic logic A non-monotonic logic is a formal logic whose conclusion relation is not monotonic. In other words, non-monotonic logics are devised to capture and represent defeasible inferences (cf. defeasible reasoning), i.e., a kind of inference in which ...
. In ASP and Datalog, logic programs have only a declarative reading, and their execution is performed by means of a proof procedure or model generator whose behaviour is not meant to be controlled by the programmer. However, in the Prolog family of languages, logic programs also have a
procedural Procedural may refer to: * Procedural generation, a term used in computer graphics applications *Procedural knowledge, the knowledge exercised in the performance of some task *Procedural law, a legal concept * Procedural memory, a cognitive scienc ...
interpretation as goal-reduction procedures: :to solve H, solve B1, and ... and solve Bn. Consider the following clause as an example: :fallible(X) :- human(X). based on an example used by
Terry Winograd Terry Allen Winograd (born February 24, 1946) is an American professor of computer science at Stanford University, and co-director of the Stanford Human–Computer Interaction Group. He is known within the philosophy of mind and artificial intell ...
to illustrate the programming language
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 desi ...
. As a clause in a logic program, it can be used both as a procedure to test whether X is fallible by testing whether X is human, and as a procedure to find an X which is fallible by finding an X which is human. Even facts have a procedural interpretation. For example, the clause: :human(socrates). can be used both as a procedure to show that socrates is human, and as a procedure to find an X that is human by "assigning" socrates to X. The declarative reading of logic programs can be used by a programmer to verify their correctness. Moreover, logic-based program transformation techniques can also be used to transform logic programs into logically equivalent programs that are more efficient. In the Prolog family of logic programming languages, the programmer can also use the known problem-solving behaviour of the execution mechanism to improve the efficiency of programs.

# History

The use of mathematical logic to represent and execute computer programs is also a feature of the
lambda calculus Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computatio ...
, developed by
Alonzo Church Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scienc ...
in the 1930s. However, the first proposal to use the clausal form of logic for representing computer programs was made by Cordell Green. This used an axiomatization of a subset of
LISP A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech. Types * A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lispi ...
, together with a representation of an input-output relation, to compute the relation by simulating the execution of the program in LISP. Foster and Elcock's
Absys Absys was an early declarative programming language from the University of Aberdeen. It anticipated a number of features of Prolog such as negation as failure, aggregation operators, the central role of backtracking and constraint solving. Abs ...
, on the other hand, employed a combination of equations and lambda calculus in an assertional programming language that places no constraints on the order in which operations are performed. Logic programming in its present form can be traced back to debates in the late 1960s and early 1970s about declarative versus procedural representations of knowledge in
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 speec ...
. Advocates of declarative representations were notably working at
Stanford Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is consid ...
, associated with John McCarthy, Bertram Raphael and Cordell Green, and in
Edinburgh Edinburgh ( ; gd, Dùn Èideann ) is the capital city of Scotland and one of its 32 council areas. Historically part of the county of Midlothian (interchangeably Edinburghshire before 1921), it is located in Lothian on the southern shore o ...
, with
John Alan Robinson John Alan Robinson (9 March 1930 – 5 August 2016) was a philosopher, mathematician, and computer scientist. He was a professor emeritus at Syracuse University. Alan Robinson's major contribution is to the foundations of automated theorem ...
Syracuse University Syracuse University (informally 'Cuse or SU) is a private research university in Syracuse, New York. Established in 1870 with roots in the Methodist Episcopal Church, the university has been nonsectarian since 1920. Located in the city's U ...
),
Pat Hayes Patrick John Hayes FAAAI (born 21 August 1944) is a British computer scientist who lives and works in the United States. , he is a Senior Research Scientist at the Institute for Human and Machine Cognition in Pensacola, Florida. Education H ...
, and Robert Kowalski. Advocates of procedural representations were mainly centered at
MIT The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...
Marvin Minsky Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive and computer scientist concerned largely with research of artificial intelligence (AI), co-founder of the Massachusetts Institute of Technology's AI laboratory, ...
and
Seymour Papert Seymour Aubrey Papert (; 29 February 1928 – 31 July 2016) was a South African-born American mathematician, computer scientist, and educator, who spent most of his career teaching and researching at MIT. He was one of the pioneers of artific ...
. Although it was based on the proof methods of logic,
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 desi ...
, developed at MIT, was the first language to emerge within this proceduralist paradigm. Planner featured pattern-directed invocation of procedural plans from goals (i.e. goal-reduction or backward chaining) and from assertions (i.e.
forward chaining Forward chaining (or forward reasoning) is one of the two main methods of reasoning when using an inference engine and can be described logically as repeated application of '' modus ponens''. Forward chaining is a popular implementation strategy ...
). The most influential implementation of Planner was the subset of Planner, called Micro-Planner, implemented by Gerry Sussman, Eugene Charniak and
Terry Winograd Terry Allen Winograd (born February 24, 1946) is an American professor of computer science at Stanford University, and co-director of the Stanford Human–Computer Interaction Group. He is known within the philosophy of mind and artificial intell ...
. It was used to implement Winograd's natural-language understanding program
SHRDLU SHRDLU was an early natural-language understanding computer program, developed by Terry Winograd at MIT in 1968–1970. In the program, the user carries on a conversation with the computer, moving objects, naming collections and querying the s ...
, which was a landmark at that time. To cope with the very limited memory systems at the time, Planner used a backtracking control structure so that only one possible computation path had to be stored at a time. Planner gave rise to the programming languages QA-4, Popler, Conniver, QLISP, and the concurrent language Ether. Hayes and Kowalski in Edinburgh tried to reconcile the logic-based declarative approach to knowledge representation with Planner's procedural approach. Hayes (1973) developed an equational language, Golux, in which different procedures could be obtained by altering the behavior of the theorem prover. Kowalski, on the other hand, developed SLD resolution, Also in Proceedings IFIP Congress, Stockholm, North Holland Publishing Co., 1974, pp. 569–574. a variant of SL-resolution, and showed how it treats implications as goal-reduction procedures. Kowalski collaborated with Colmerauer in Marseille, who developed these ideas in the design and implementation of the programming language
Prolog Prolog is a logic programming language associated with artificial intelligence and computational linguistics. Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primaril ...
. The
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 ...
was founded to promote Logic Programming in 1986. Prolog gave rise to the programming languages ALF,
Fril Fril is a programming language for first-order predicate calculus. It includes the semantics of Prolog as a subset, but takes its syntax from the of Logic Programming Associates and adds support for fuzzy sets, support logic, and metaprogramm ...
, Gödel,
Mercury Mercury commonly refers to: * Mercury (planet), the nearest planet to the Sun * Mercury (element), a metallic chemical element with the symbol Hg * Mercury (mythology), a Roman god Mercury or The Mercury may also refer to: Companies * Mercu ...
, Oz,
Ciao ''Ciao'' ( , ) is an informal salutation in the Italian language that is used for both "hello" and "goodbye". Originally from the Venetian language, it has entered the vocabulary of English and of many other languages around the world. Its d ...
,
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 ...
, XSB, and λProlog, as well as a variety of concurrent logic programming languages,
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 cl ...
languages and
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 ...
.

# Concepts

## Semantics

Maarten van Emden and Robert Kowalski defined three semantics for Horn clause logic programs, model-theoretic, fixed-point, and proof-theoretic, and showed that they are equivalent.

## Logic and control

Logic programming can be viewed as controlled deduction. An important concept in logic programming is the separation of programs into their logic component and their control component. With pure logic programming languages, the logic component alone determines the solutions produced. The control component can be varied to provide alternative ways of executing a logic program. This notion is captured by the slogan :Algorithm = Logic + Control where "Logic" represents a logic program and "Control" represents different theorem-proving strategies.

## Problem solving

In the simplified, propositional case in which a logic program and a top-level atomic goal contain no variables, backward reasoning determines an and-or tree, which constitutes the search space for solving the goal. The top-level goal is the root of the tree. Given any node in the tree and any clause whose head matches the node, there exists a set of child nodes corresponding to the sub-goals in the body of the clause. These child nodes are grouped together by an "and". The alternative sets of children corresponding to alternative ways of solving the node are grouped together by an "or". Any search strategy can be used to search this space. Prolog uses a sequential, last-in-first-out, backtracking strategy, in which only one alternative and one sub-goal is considered at a time. Other search strategies, such as parallel search, intelligent backtracking, or best-first search to find an optimal solution, are also possible. In the more general case, where sub-goals share variables, other strategies can be used, such as choosing the subgoal that is most highly instantiated or that is sufficiently instantiated so that only one procedure applies. Such strategies are used, for example, in
concurrent logic programming Concurrent logic programming is a variant of logic programming in which programs are sets of guarded Horn clauses of the form: : The conjunction is called the guard of the clause, and is the commitment operator. Declaratively, guarded Hor ...
.

## Negation as failure

For most practical applications, as well as for applications that require non-monotonic reasoning in artificial intelligence, Horn clause logic programs need to be extended to normal logic programs with negative conditions. A ''clause'' in a normal logic program has the form: :H :- A1, …, An, not B1, …, not Bn. and is read declaratively as a logical implication: :H if A1 and … and An and not B1 and … and not Bn. where H and all the Ai and Bi are atomic formulas. The negation in the negative literals not Bi is commonly referred to as "
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 ...
", because in most implementations, a negative condition not Bi is shown to hold by showing that the positive condition Bi fails to hold. For example: canfly(X) :- bird(X), not abnormal(X). abnormal(X) :- wounded(X). bird(john). bird(mary). wounded(john). Given the goal of finding something that can fly: :- canfly(X). there are two candidate solutions, which solve the first subgoal bird(X), namely X = john and X = mary. The second subgoal not abnormal(john) of the first candidate solution fails, because wounded(john) succeeds and therefore abnormal(john) succeeds. However, the second subgoal not abnormal(mary) of the second candidate solution succeeds, because wounded(mary) fails and therefore abnormal(mary) fails. Therefore, X = mary is the only solution of the goal. Micro-Planner had a construct, called "thnot", which when applied to an expression returns the value true if (and only if) the evaluation of the expression fails. An equivalent operator typically exists in modern
Prolog Prolog is a logic programming language associated with artificial intelligence and computational linguistics. Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primaril ...
's implementations. It is typically written as not(''Goal'') or \+ ''Goal'', where ''Goal'' is some goal (proposition) to be proved by the program. This operator differs from negation in first-order logic: a negation such as \+ X 1 fails when the variable X has been bound to the atom 1, but it succeeds in all other cases, including when X is unbound. This makes Prolog's reasoning non-monotonic: X = 1, \+ X 1 always fails, while \+ X 1, X = 1 can succeed, binding X to 1, depending on whether X was initially bound (note that standard Prolog executes goals in left-to-right order). The logical status of negation as failure was unresolved until Keith Clark
978 Year 978 ( CMLXXVIII) was a common year starting on Tuesday (link will display the full calendar) of the Julian calendar. Events By place Byzantine Empire * Battle of Pankaleia: Rebel forces under General Bardas Skleros are defeat ...
showed that, under certain natural conditions, it is a correct (and sometimes complete) implementation of classical negation with respect to the completion of the program. Completion amounts roughly to regarding the set of all the program clauses with the same predicate on the left hand side, say :H :- Body1. : :H :- Bodyk. as a definition of the predicate :H iff (Body1 or … or Bodyk) where "iff" means "if and only if". Writing the completion also requires explicit use of the equality predicate and the inclusion of a set of appropriate axioms for equality. However, the implementation of negation as failure needs only the if-halves of the definitions without the axioms of equality. For example, the completion of the program above is: :canfly(X) iff bird(X), not abnormal(X). :abnormal(X) iff wounded(X). : bird(X) iff X = john or X = mary. : X = X. : not john = mary. : not mary = john. The notion of completion is closely related to McCarthy's
circumscription Circumscription may refer to: *Circumscribed circle *Circumscription (logic) *Circumscription (taxonomy) * Circumscription theory, a theory about the origins of the political state in the history of human evolution proposed by the American anthrop ...
semantics for default reasoning, and to the closed world assumption. As an alternative to the completion semantics, negation as failure can also be interpreted epistemically, as in the
stable model semantics The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program c ...
of answer set programming. In this interpretation not(Bi) means literally that Bi is not known or not believed. The epistemic interpretation has the advantage that it can be combined very simply with classical negation, as in "extended logic programming", to formalise such phrases as "the contrary can not be shown", where "contrary" is classical negation and "can not be shown" is the epistemic interpretation of negation as failure.

## Knowledge representation

The fact that Horn clauses can be given a procedural interpretation and, vice versa, that goal-reduction procedures can be understood as Horn clauses + backward reasoning means that logic programs combine declarative and procedural representations of
knowledge Knowledge can be defined as awareness of facts or as practical skills, and may also refer to familiarity with objects or situations. Knowledge of facts, also called propositional knowledge, is often defined as true belief that is dist ...
. The inclusion of
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 ...
means that logic programming is a kind of
non-monotonic logic A non-monotonic logic is a formal logic whose conclusion relation is not monotonic. In other words, non-monotonic logics are devised to capture and represent defeasible inferences (cf. defeasible reasoning), i.e., a kind of inference in which ...
. Despite its simplicity compared with classical logic, this combination of Horn clauses and negation as failure has proved to be surprisingly expressive. For example, it provides a natural representation for the common-sense laws of cause and effect, as formalised by both the
situation calculus The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains. It was first introduced by John McCarthy in 1963. The main version of the situational calculus that is presented in this article is based o ...
and
event calculus The event calculus is a logical language for representing and reasoning about events and their effects first presented by Robert Kowalski and Marek Sergot in 1986. It was extended by Murray Shanahan and Rob Miller in the 1990s. Similar to other ...
. It has also been shown to correspond quite naturally to the semi-formal language of legislation. In particular, Prakken and Sartor credit the representation of the British Nationality Act as a logic program with being "hugely influential for the development of computational representations of legislation, showing how logic programming enables intuitively appealing representations that can be directly deployed to generate automatic inferences".

# Variants and extensions

## Prolog

The programming language
Prolog Prolog is a logic programming language associated with artificial intelligence and computational linguistics. Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primaril ...
was developed in 1972 by Alain Colmerauer. It emerged from a collaboration between Colmerauer in
Marseille Marseille ( , , ; also spelled in English as Marseilles; oc, Marselha ) is the prefecture of the French department of Bouches-du-Rhône and capital of the Provence-Alpes-Côte d'Azur region. Situated in the camargue region of southern F ...
and Robert Kowalski in Edinburgh. Colmerauer was working on
natural-language understanding Natural-language understanding (NLU) or natural-language interpretation (NLI) is a subtopic of natural-language processing in artificial intelligence that deals with machine reading comprehension. Natural-language understanding is considered an AI ...
, using logic to represent semantics and using resolution for question-answering. During the summer of 1971, Colmerauer and Kowalski discovered that the clausal form of logic could be used to represent formal grammars and that resolution theorem provers could be used for parsing. They observed that some theorem provers, like hyper-resolution, behave as bottom-up parsers and others, like SL-resolution (1971), behave as top-down parsers. It was in the following summer of 1972, that Kowalski, again working with Colmerauer, developed the procedural interpretation of implications. This dual declarative/procedural interpretation later became formalised in the Prolog notation :H :- B1, …, Bn. which can be read (and used) both declaratively and procedurally. It also became clear that such clauses could be restricted to definite clauses or Horn clauses, where H, B1, ..., Bn are all atomic predicate logic formulae, and that SL-resolution could be restricted (and generalised) to LUSH or SLD-resolution. Kowalski's procedural interpretation and LUSH were described in a 1973 memo, published in 1974. Colmerauer, with Philippe Roussel, used this dual interpretation of clauses as the basis of Prolog, which was implemented in the summer and autumn of 1972. The first Prolog program, also written in 1972 and implemented in Marseille, was a French question-answering system. The use of Prolog as a practical programming language was given great momentum by the development of a compiler by David Warren in Edinburgh in 1977. Experiments demonstrated that Edinburgh Prolog could compete with the processing speed of other symbolic programming languages such as
Lisp A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech. Types * A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lispi ...
. Edinburgh Prolog became the ''de facto'' standard and strongly influenced the definition of
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 * Is ...
standard Prolog.

## Abductive logic programming

Abductive logic programming is an extension of normal Logic Programming that allows some predicates, declared as abducible predicates, to be "open" or undefined. A clause in an abductive logic program has the form: :H :- B1, …, Bn, A1, …, An. where H is an atomic formula that is not abducible, all the Bi are literals whose predicates are not abducible, and the Ai are atomic formulas whose predicates are abducible. The abducible predicates can be constrained by integrity constraints, which can have the form: :false :- L1, …, Ln. where the Li are arbitrary literals (defined or abducible, and atomic or negated). For example: canfly(X) :- bird(X), normal(X). false :- normal(X), wounded(X). bird(john). bird(mary). wounded(john). where the predicate normal is abducible. Problem-solving is achieved by deriving hypotheses expressed in terms of the abducible predicates as solutions to problems to be solved. These problems can be either observations that need to be explained (as in classical
abductive reasoning Abductive reasoning (also called abduction,For example: abductive inference, or retroduction) is a form of logical inference formulated and advanced by American philosopher Charles Sanders Peirce beginning in the last third of the 19th centu ...
) or goals to be solved (as in normal logic programming). For example, the hypothesis normal(mary) explains the observation canfly(mary). Moreover, the same hypothesis entails the only solution X = mary of the goal of finding something which can fly: :- canfly(X). Abductive logic programming has been used for fault diagnosis, planning, natural language processing and machine learning. It has also been used to interpret Negation as Failure as a form of abductive reasoning.

## Metalogic programming

Because mathematical logic has a long tradition of distinguishing between object language and
metalanguage In logic and linguistics, a metalanguage is a language used to describe another language, often called the ''object language''. Expressions in a metalanguage are often distinguished from those in the object language by the use of italics, quota ...
, logic programming also allows metalevel programming. The simplest metalogic program is the so-called "
vanilla Vanilla is a spice derived from orchids of the genus '' Vanilla'', primarily obtained from pods of the Mexican species, flat-leaved vanilla ('' V. planifolia''). Pollination is required to make the plants produce the fruit from which ...
" meta-interpreter: solve(true). solve((A,B)):- solve(A),solve(B). solve(A):- clause(A,B),solve(B). where true represents an empty conjunction, and clause(A,B) means that there is an object-level clause of the form A :- B. Metalogic programming allows object-level and metalevel representations to be combined, as in natural language. It can also be used to implement any logic which is specified as
inference rule In the philosophy of logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises, analyzes their syntax, and returns a conclusion (or conclusions). For example, the rule of ...
s. Metalogic is used in logic programming to implement metaprograms, which manipulate other programs, databases, knowledge bases or axiomatic theories as data.

## Constraint logic programming

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 cl ...
combines Horn clause logic programming with constraint solving. It extends Horn clauses by allowing some predicates, declared as constraint predicates, to occur as literals in the body of clauses. A constraint logic program is a set of clauses of the form: :H :- C1, …, Cn ◊ B1, …, Bn. where H and all the Bi are atomic formulas, and the Ci are constraints. Declaratively, such clauses are read as ordinary logical implications: :H if C1 and … and Cn and B1 and … and Bn. However, whereas the predicates in the heads of clauses are defined by the constraint logic program, the predicates in the constraints are predefined by some domain-specific model-theoretic structure or theory. Procedurally, subgoals whose predicates are defined by the program are solved by goal-reduction, as in ordinary logic programming, but constraints are checked for satisfiability by a domain-specific constraint-solver, which implements the semantics of the constraint predicates. An initial problem is solved by reducing it to a satisfiable conjunction of constraints. The following constraint logic program represents a toy temporal database of john's history as a teacher: teaches(john, hardware, T) :- 1990 ≤ T, T < 1999. teaches(john, software, T) :- 1999 ≤ T, T < 2005. teaches(john, logic, T) :- 2005 ≤ T, T ≤ 2012. rank(john, instructor, T) :- 1990 ≤ T, T < 2010. rank(john, professor, T) :- 2010 ≤ T, T < 2014. Here and < are constraint predicates, with their usual intended semantics. The following goal clause queries the database to find out when john both taught logic and was a professor: ::- teaches(john, logic, T), rank(john, professor, T). The solution is 2010 ≤ T, T ≤ 2012. Constraint logic programming has been used to solve problems in such fields as
civil engineering Civil engineering is a professional engineering discipline that deals with the design, construction, and maintenance of the physical and naturally built environment, including public works such as roads, bridges, canals, dams, airports, sew ...
,
mechanical engineering Mechanical engineering is the study of physical machines that may involve force and movement. It is an engineering branch that combines engineering physics and mathematics principles with materials science, to design, analyze, manufacture, ...
,
digital circuit In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematic ...
verification, automated timetabling,
air traffic control Air traffic control (ATC) is a service provided by ground-based air traffic controllers who direct aircraft on the ground and through a given section of controlled airspace, and can provide advisory services to aircraft in non-controlled air ...
, and finance. It is closely related to abductive logic programming.

## Concurrent logic programming

Concurrent logic programming integrates concepts of logic programming with
concurrent programming Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to: Law * Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea'' * Concurring opinion (also called a "concurrence"), a ...
. Its development was given a big impetus in the 1980s by its choice for the systems programming language of the Japanese Fifth Generation Project (FGCS). A concurrent logic program is a set of guarded
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 lo ...
of the form: ::H :- G1, …, Gn , B1, …, Bn. The conjunction G1, ... , Gn is called the
guard Guard or guards may refer to: Professional occupations * Bodyguard, who protects an individual from personal assault * Crossing guard, who stops traffic so pedestrians can cross the street * Lifeguard, who rescues people from drowning * Prison ...
of the clause, and , is the commitment operator. Declaratively, guarded Horn clauses are read as ordinary logical implications: ::H if G1 and … and Gn and B1 and … and Bn. However, procedurally, when there are several clauses whose heads H match a given goal, then all of the clauses are executed in parallel, checking whether their guards G1, ... , Gn hold. If the guards of more than one clause hold, then a committed choice is made to one of the clauses, and execution proceeds with the subgoals B1, ..., Bn of the chosen clause. These subgoals can also be executed in parallel. Thus concurrent logic programming implements a form of "don't care nondeterminism", rather than "don't know nondeterminism". For example, the following concurrent logic program defines a predicate shuffle(Left, Right, Merge) , which can be used to shuffle two lists Left and Right, combining them into a single list Merge that preserves the ordering of the two lists Left and Right: shuffle([], [], []). shuffle(Left, Right, Merge) :- Left = Rest, Merge = ShortMerge shuffle(Rest, Right, ShortMerge). shuffle(Left, Right, Merge) :- Right = Rest, Merge = ShortMerge shuffle(Left, Rest, ShortMerge). Here, [] represents the empty list, and [Head , Tail] represents a list with first element Head followed by list Tail, as in Prolog. (Notice that the first occurrence of , in the second and third clauses is the list constructor, whereas the second occurrence of , is the commitment operator.) The program can be used, for example, to shuffle the lists ce, queen, king/kbd> and , 4, 2/kbd> by invoking the goal clause: shuffle( ce, queen, king , 4, 2 Merge). The program will non-deterministically generate a single solution, for example Merge = ce, queen, 1, king, 4, 2/kbd>. Arguably, concurrent logic programming is based on message passing, so it is subject to the same indeterminacy as other concurrent message-passing systems, such as
Actors An actor or actress is a person who portrays a character in a performance. The actor performs "in the flesh" in the traditional medium of the theatre or in modern media such as film, radio, and television. The analogous Greek term is (), lit ...
(see Indeterminacy in concurrent computation). Carl Hewitt has argued that concurrent logic programming is not based on logic in his sense that computational steps cannot be logically deduced. However, in concurrent logic programming, any result of a terminating computation is a logical consequence of the program, and any partial result of a partial computation is a logical consequence of the program and the residual goal (process network). Thus the indeterminacy of computations implies that not all logical consequences of the program can be deduced.

## 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 (or in addition to) solving constraint satisfaction problems. Goals in constraint logic programmi ...
combines concurrent logic programming and
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 cl ...
, using constraints to control concurrency. A clause can contain a guard, which is a set of constraints that may block the applicability of the clause. When the guards of several clauses are satisfied, concurrent constraint logic programming makes a committed choice to use only one.

## Inductive logic programming

Inductive logic programming is concerned with generalizing positive and negative examples in the context of background knowledge:
machine learning Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence. Machine ...
of logic programs. Recent work in this area, combining logic programming, learning and probability, has given rise to the new field of statistical relational learning and probabilistic inductive logic programming.

## Higher-order logic programming

Several researchers have extended logic programming with higher-order programming features derived from
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 expre ...
, such as predicate variables. Such languages include the Prolog extensions
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, H ...
and λProlog.

## Linear logic programming

Basing logic programming within
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. Although the logic has also ...
has resulted in the design of logic programming languages that are considerably more expressive than those based on classical logic. Horn clause programs can only represent state change by the change in arguments to predicates. In linear logic programming, one can use the ambient linear logic to support state change. Some early designs of logic programming languages based on linear logic include LO, Lolli, ACL, and Forum. Forum provides a goal-directed interpretation of all linear logic.

## Object-oriented logic programming

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 well-d ...
extends logic programming with objects and the frame syntax.
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. ...
extends the Prolog programming language with support for objects, protocols, and other OOP concepts. It supports most standard-compliant Prolog systems as backend compilers.

## Transaction logic programming

Transaction logic is an extension of logic programming with a logical theory of state-modifying updates. It has both a model-theoretic semantics and a procedural one. An implementation of a subset of Transaction logic is available in the
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 Progr ...
system. Other prototypes are also available.

*
Automated 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 ma ...
*
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 cl ...
*
Control theory Control theory is a field of mathematics that deals with the control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to ...
*
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 ...
*
Fril Fril is a programming language for first-order predicate calculus. It includes the semantics of Prolog as a subset, but takes its syntax from the of Logic Programming Associates and adds support for fuzzy sets, support logic, and metaprogramm ...
*
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 ...
*
Fuzzy logic Fuzzy logic is a form of many-valued logic in which the truth value of variables may be any real number between 0 and 1. It is employed to handle the concept of partial truth, where the truth value may range between completely true and complete ...
* Inductive logic programming * Logic in computer science (includes
Formal methods In computer science, formal methods are mathematically rigorous techniques for the specification, development, and verification of software and hardware systems. The use of formal methods for software and hardware design is motivated by the expe ...
) *
Logic programming languages 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 ...
*
Programmable logic controller A programmable logic controller (PLC) or programmable controller is an industrial computer that has been ruggedized and adapted for the control of manufacturing processes, such as assembly lines, machines, robotic devices, or any activity ...
* R++ * Reasoning system * Rule-based machine learning *
Satisfiability In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...
**
Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
*
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. Although the logic has also ...

# Sources

* *

*

## Other sources

* John McCarthy
"Programs with common sense"
''Symposium on Mechanization of Thought Processes''. National Physical Laboratory. Teddington, England. 1958. * * Ehud Shapiro (Editor). ''Concurrent Prolog''. MIT Press. 1987. * James Slagle
"Experiments with a Deductive Question-Answering Program"
CACM. December 1965. * Dov Gabbay, Gabbay, Dov M.; Hogger, Christopher John; Robinson, J.A., eds. (1993-1998)
Handbook of Logic in Artificial Intelligence and Logic Programming
Vols. 1–5, Oxford University Press.

* Carl Hewitt.
Procedural Embedding of Knowledge in Planner
. IJCAI 1971. * Carl Hewitt.
The Repeated Demise of Logic Programming and Why It Will Be Reincarnated
. ''AAAI Spring Symposium: What Went Wrong and Why: Lessons from AI Research and Applications'' 2006: 2–9. * Evgeny Dantsin, Thomas , Georg Gottlob, Andrei Voronkov
Complexity and expressive power of logic programming
ACM Comput. Surv. 33(3): 374–425 (2001) * Ulf Nilsson and Jan Maluszynski
Logic, Programming and Prolog