logic programming rulebased redirects here for the method of machine translation see rulebased machine translation for methods of machine learning see rulebased machine learning programming paradigms action agentoriented arrayoriented automatabased concurrent computing relativistic programming datadriven declarative contrast imperative functional functional logic purely functional logic abductive logic answer set concurrent logic functional logic inductive logic constraint constraint logic concurrent constraint logic dataflow flowbased reactive dynamicscripting eventdriven functionlevel contrast valuelevel pointfree style concatenative generic imperative contrast declarative procedural objectoriented literate languageoriented naturallanguage programming disciplinespecific domainspecific grammaroriented intentional metaprogramming automatic inductive programming reflective attributeoriented macro template nonstructured contrast structured array nondeterministic parallel computing processoriented probabilistic stackbased structured contrast nonstructured blockstructured objectoriented actorbased classbased concurrent prototypebased by separation of concerns aspectoriented roleoriented subjectoriented recursive symbolic valuelevel contrast functionlevel quantum programming vte logic programming is a type of 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 programming language families include prolog answer set programming asp and datalog in all of these languages rules are written in the form of clauses 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 formulae these clauses are called definite clauses or horn clauses however there exist 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 formulae logic programming languages that include this extension have the knowledge representation capabilities of a nonmonotonic logic 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 under the control of the programmer however in the prolog family of languages logic programs also have a procedural interpretation as goalreduction procedures to solve h solve b1 and and solve bn consider for example the following clause falliblex humanx based on an example used by terry winograd to illustrate the programming language planner 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 that is fallible by finding an x that is human even facts have a procedural interpretation for example the clause humansocrates 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 logicbased 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 problemsolving 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 developed by alonzo church in the 1930s however the first proposal to use the clausal form of logic for representing computer programs was made by cordell green 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 advocates of declarative representations were notably working at stanford associated with john mccarthy bertram raphael and cordell green and in edinburgh with john alan robinson an academic visitor from syracuse university pat hayes and robert kowalski advocates of procedural representations were mainly centered at mit under the leadership of marvin minsky and seymour papert although it was based on the proof methods of logic planner developed at mit was the first language to emerge within this proceduralist paradigm hayes and kowalski in edinburgh tried to reconcile the logicbased declarative approach to knowledge representation with planners procedural approach hayes 1973 developed an equational language golux in which different procedures could be obtained by altering the behavior of the theorem prover and showed how it treats implications as goalreduction procedures kowalski collaborated with colmerauer in marseille who developed these ideas in the design and implementation of the programming language prolog the association for logic programming was founded to promote logic programming in 1986 prolog gave rise to the programming languages alf fril gdel mercury oz ciao visual prolog xsb and prolog as well as a variety of concurrent logic programming languages concepts logic and control declarative programming 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 theoremproving strategies problem solving in the simplified propositional case in which a logic program and a toplevel atomic goal contain no variables backward reasoning determines an andor tree which constitutes the search space for solving the goal the toplevel 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 subgoals 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 lastinfirstout backtracking strategy in which only one alternative and one subgoal is considered at a time other search strategies such as parallel search intelligent backtracking or bestfirst search to find an optimal solution are also possible in the more general case where subgoals 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 negation as failure negation as failure for most practical applications as well as for applications that require nonmonotonic 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 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 canflyx birdx not abnormalx abnormalx woundedx birdjohn birdmary woundedjohn given the goal of finding something that can fly canflyx there are two candidate solutions which solve the first subgoal birdx namely x john and x mary the second subgoal not abnormaljohn of the first candidate solution fails because woundedjohn succeeds and therefore abnormaljohn succeeds however the second subgoal not abnormalmary of the second candidate solution succeeds because woundedmary fails and therefore abnormalmary fails therefore x mary is the only solution of the goal microplanner 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 is normally builtin in modern prologs implementations it is normally written as notgoal or goal where goal is some goal proposition to be proved by the program this operator differs from negation in firstorder 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 prologs reasoning nonmonotonic 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 lefttoright order the logical status of negation as failure was unresolved until keith clark 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 by failure needs only the ifhalves of the definitions without the axioms of equality for example the completion of the program above is canflyx iff birdx not abnormalx abnormalx iff woundedx birdx iff x john or x mary x x not john mary not mary john the notion of completion is closely related to mccarthys circumscription 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 of answer set programming in this interpretation notbi 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 goalreduction procedures can be understood as horn clauses backward reasoning means that logic programs combine declarative and procedural representations of knowledge the inclusion of negation as failure means that logic programming is a kind of nonmonotonic logic 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 commonsense laws of cause and effect as formalised by both the situation calculus and event calculus it has also been shown to correspond quite naturally to the semiformal language of legislation in particular prakken and sartor 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 prolog the programming language prolog was developed in 1972 by alain colmerauer it emerged from a collaboration between colmerauer in marseille and robert kowalski in edinburgh colmerauer was working on natural language understanding using logic to represent semantics and using resolution for questionanswering 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 hyperresolution behave as bottomup parsers and others like slresolution 1971 behave as topdown parsers it was in the following summer of 1972 that kowalski again working with colmerauer developed the procedural interpretation of implications this dual declarativeprocedural 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 slresolution could be restricted and generalised to lush or sldresolution kowalskis 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 questionanswering 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 edinburgh prolog became the de facto standard and strongly influenced the definition of iso 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 b1 bn where the bi are arbitrary literals defined or abducible and atomic or negated for example canflyx birdx normalx false normalx woundedx birdjohn birdmary woundedjohn where the predicate normal is abducible problem solving is achieved by deriving hypotheses expressed in terms of the abducible predicates as solutions of problems to be solved these problems can be either observations that need to be explained as in classical abductive reasoning or goals to be solved as in normal logic programming for example the hypothesis normalmary explains the observation canflymary moreover the same hypothesis entails the only solution x mary of the goal of finding something that can fly canflyx 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 logic programming also allows metalevel programming the simplest metalogic program is the socalled vanilla metainterpreter solvetrue solveab solveasolveb solvea clauseabsolveb where true represents an empty conjunction and clauseab means there is an objectlevel clause of the forma b metalogic programming allows objectlevel and metalevel representations to be combined as in natural language it can also be used to implement any logic that is specified by means of inference rules 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 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 domainspecific modeltheoretic structure or theory procedurally subgoals whose predicates are defined by the program are solved by goalreduction as in ordinary logic programming but constraints are checked for satisfiability by a domainspecific constraintsolver 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 johns history as a teacher teachesjohn hardware t 1990 t t 1999 teachesjohn software t 1999 t t 2005 teachesjohn logic t 2005 t t 2012 rankjohn instructor t 1990 t t 2010 rankjohn 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 teachesjohn logic t rankjohn professor t the solution is 2010 t t 2012 constraint logic programming has been used to solve problems in such fields as civil engineering mechanical engineering digital circuit verification automated timetabling air traffic control and finance it is closely related to abductive logic programming concurrent logic programming concurrent logic programming concurrent logic programming integrates concepts of logic programming with concurrent programming 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 of the form h g1 gn b1 bn the conjunction g1 gn is called the guard 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 proceedes 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 dont care nondeterminism rather than dont know nondeterminism for example the following concurrent logic program defines a predicate shuffleleft 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 shuffleleft right merge left merge shufflerest right shortmerge shuffleleft right merge right merge shuffleleft rest shortmerge here by invoking the goal clause shuffle merge the program will nondeterministically generate a single solution for example merge arguably concurrent logic programming is based on message passing and consequently is subject to the same indeterminacy as other concurrent messagepassing systems such as actors 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 concurrent constraint logic programming concurrent constraint logic programming concurrent constraint logic programming combines concurrent logic programming and constraint logic programming 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 the use of only one inductive logic programming inductive logic programming inductive logic programming is concerned with generalizing positive and negative examples in the context of background knowledge machine learning 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 higherorder logic programming several researchers have extended logic programming with higherorder programming features derived from higherorder logic such as predicate variables such languages include the prolog extensions hilog and prolog linear logic programming basing logic programming within linear logic 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 forum provides a goaldirected interpretation of all of linear logic objectoriented logic programming flogic extends logic programming with objects and the frame syntax logtalk extends the prolog programming language with support for objects protocols and other oop concepts highly portable it supports most standardcompliant prolog systems as backend compilers transaction logic programming transaction logic is an extension of logic programming with a logical theory of statemodifying updates it has both a modeltheoretic semantics and a procedural one an implementation of a subset of transaction logic is available in the flora2 system other prototypes are also available automated theorem proving boolean satisfiability problem constraint logic programming datalog fril functional programming fuzzy logic inductive logic programming logic in computer science includes formal methods logic programming languages programming paradigm r reasoning system rulebased machine learning satisfiability general introductions baral c gelfond m 1994 logic programming and knowledge representation pdf the journal of logic programming 1920 73148 doi1010160743106694900256 robert kowalski the early years of logic programming kowalski r a 1988 the early years of logic programming pdf communications of the acm 31 3843 doi1011453504335046 lloyd j w 1987 foundations of logic programming 2nd edition springerverlag other sources john mccarthy programs with common sense symposium on mechanization of thought processes national physical laboratory teddington england 1958 d miller g nadathur f pfenning a scedrov uniform proofs as a foundation for logic programming annals of pure and applied logic vol 51 pp 125157 1991 ehud shapiro editor concurrent prolog mit press 1987 james slagle experiments with a deductive questionanswering program cacm december 1965 carl hewitt procedural embedding of knowledge in planner ijcai 1971 carl hewitt the repeated demise of logic programming and why it will be reincarnated evgeny dantsin thomas eiter georg gottlob andrei voronkov complexity and expressive power of logic programming acm comput surv 333 374425 2001 ulf nilsson and jan maluszynski logic programming and prolog wikimedia commons has media related to logic programming logic programming virtual library entry bibliographies on logic programming association for logic programming alp theory and practice of logic programming journal logic programming in c with castor logic programming in oz prolog development center racklog logic programming in racket vtetypes of programming languages actorbased array aspectoriented classbased concatenative concurrent dataflow declarative domainspecific dynamic esoteric eventdriven extensible functional imperative logic macro metaprogramming multiparadigm objectbased objectoriented pipeline procedural prototypebased reflective rulebased scripting stack based synchronous templating assembly compiled interpreted machine lowlevel highlevel very highlevel first generation second generation third generation fourth generation fifth generation nonenglishbased visual vtecomputable knowledgetopics andconcepts alphabet of human thought authority control automated reasoning commonsense knowledge commonsense reasoning computability formal system inference engine knowledge base knowledgebased systems knowledge engineering knowledge extraction knowledge representation knowledge retrieval library classification logic programming ontology personal knowledge base question answering semantic reasoner proposals andimplementations zairja ars magna1300 an essay towards a real character and a philosophical language1688 calculus ratiocinator and characteristica universalis1700 dewey decimal classification1876 begriffsschrift1879 mundaneum1910 logical atomism1918 tractatus logicophilosophicus1921 hilberts program1920s incompleteness theorem1931 world brain1938 memex1945 general problem solver1959 prolog1972 cyc1984 semantic web2001 evi2007 wolfram alpha2009 watson2011 siri2011 knowledge graph2012 wikidata2012 cortana2014 viv2016 in fiction the engine gullivers travels 1726 joe a logic named joe 1946 the librarian snow crash 1992 dr know ai artificial intelligence 2001 waterhouse the baroque cycle 2003 see also logic machines in fiction and list of fictional computers authority control bne xx550687 bnf cb12067891q data gnd 41950963 lccn sh86003454 