logic programming
In plain wordsA style of programming in which you write down facts and rules in logic and then ask questions; the computer works out the answers itself by logical deduction.
A declarative style of programming in which code is read as a logical theory — facts and rules, usually Horn clausesHorn clause, n.: A simple, restricted form of logical rule ('if these conditions all hold, then this one conclusion holds') that computers can reason with very efficiently. — and a query is answered by deduction, the system searching for variable bindings under which the query follows from the theory. Robert Kowalski summarized the idea as 'algorithm = logic + control': the programmer states what is true, and an execution strategy, such as PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs.'s depth-first SLD resolutionresolution, n.: A mechanical step of logical reasoning: from 'A or B' and 'not A or C', conclude 'B or C'. Repeating it can demonstrate any conclusion that genuinely follows from what is known. with unificationunification, n.: Finding values for the blanks in two logical patterns so that they become identical, for example matching 'parent(X, bob)' with 'parent(alice, Y)' by setting X to alice and Y to bob. and backtracking, determines how answers are found. Negation is usually treated as negation as failure — 'not p' succeeds if p cannot be proven — under a closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it.. Major branches include Prolog, DatalogDatalog, prop. n.: A small logic language for asking questions of a database with rules, including rules that refer to themselves, such as 'X is an ancestor of Y if X is a parent of an ancestor of Y'., constraint logic programming, answer set programminganswer set programming, n.: A way to solve hard puzzles and scheduling problems by describing in logical rules what a valid solution looks like; a solver then finds the arrangements that fit those rules. and inductive logic programminginductive logic programming, n.: A kind of machine learning that discovers general logical rules — such as 'X is a grandparent of Z if X is a parent of a parent of Z' — from examples and background knowledge., which learns logic programs from examples.
In logic programming you describe the family tree and simply ask who Ann's cousins are.
Origin
Emerged in 1972–1974 from collaboration between Alain Colmerauer and Philippe Roussel in Marseille, who created Prolog, and Robert Kowalski in Edinburgh, who gave Horn-clause resolution a procedural interpretation; Cordell Green's 1969 question-answering work was a precursor. Japan's Fifth Generation Computer Systems projectFifth Generation Computer Systems project, prop. n.: Japan's government-backed effort, from 1982 to 1992, to build a new kind of computer that reasons with logic using many processors at once. It fell short, but it alarmed other countries into launching AI programs of their own. (1982–1992) made logic programming a national research bet.
Related
- PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs.
- Horn clauseHorn clause, n.: A simple, restricted form of logical rule ('if these conditions all hold, then this one conclusion holds') that computers can reason with very efficiently.
- DatalogDatalog, prop. n.: A small logic language for asking questions of a database with rules, including rules that refer to themselves, such as 'X is an ancestor of Y if X is a parent of an ancestor of Y'.
- answer set programminganswer set programming, n.: A way to solve hard puzzles and scheduling problems by describing in logical rules what a valid solution looks like; a solver then finds the arrangements that fit those rules.
- inductive logic programminginductive logic programming, n.: A kind of machine learning that discovers general logical rules — such as 'X is a grandparent of Z if X is a parent of a parent of Z' — from examples and background knowledge.
- resolutionresolution, n.: A mechanical step of logical reasoning: from 'A or B' and 'not A or C', conclude 'B or C'. Repeating it can demonstrate any conclusion that genuinely follows from what is known.
- unificationunification, n.: Finding values for the blanks in two logical patterns so that they become identical, for example matching 'parent(X, bob)' with 'parent(alice, Y)' by setting X to alice and Y to bob.
Sources
- Kowalski, R. (1974). Predicate Logic as Programming Language. Proceedings of IFIP Congress 74, 569–574.
- Kowalski, R. (1979). Algorithm = Logic + Control. Communications of the ACM 22(7), 424–436.
Mentioned in
abductive reasoningabductive reasoning, n.: Reasoning from an observation to its most likely explanation — the grass is wet, so it probably rained — the kind of educated guess that doctors and detectives make., deductive reasoningdeductive reasoning, n.: Reasoning in which true starting points guarantee a true conclusion: if every square is a rectangle and this shape is a square, then it must be a rectangle., first-order logicfirst-order logic, n.: A precise formal language for statements about objects and their relations, using 'for all' and 'there exists', such as 'every person has a mother'. It is the standard logic of mathematics and of classic AI., knowledge representationknowledge representation, n.: The study of how to record knowledge about objects, categories, rules and events in a precise format, so that a program can reason with it and reach conclusions nobody typed in., LispLisp, prop. n.: A programming language invented in 1958 for AI research, in which programs and data are written the same way, as nested lists in parentheses. It was the main language of AI for decades., PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs., answer set programminganswer set programming, n.: A way to solve hard puzzles and scheduling problems by describing in logical rules what a valid solution looks like; a solver then finds the arrangements that fit those rules., closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it., DatalogDatalog, prop. n.: A small logic language for asking questions of a database with rules, including rules that refer to themselves, such as 'X is an ancestor of Y if X is a parent of an ancestor of Y'., Fifth Generation Computer Systems projectFifth Generation Computer Systems project, prop. n.: Japan's government-backed effort, from 1982 to 1992, to build a new kind of computer that reasons with logic using many processors at once. It fell short, but it alarmed other countries into launching AI programs of their own., Horn clauseHorn clause, n.: A simple, restricted form of logical rule ('if these conditions all hold, then this one conclusion holds') that computers can reason with very efficiently., inductive logic programminginductive logic programming, n.: A kind of machine learning that discovers general logical rules — such as 'X is a grandparent of Z if X is a parent of a parent of Z' — from examples and background knowledge., non-monotonic reasoningnon-monotonic reasoning, n.: Reasoning in which new information can overturn earlier conclusions — you assume a bird can fly until you learn it is a penguin — as people do constantly but classical logic does not allow., resolutionresolution, n.: A mechanical step of logical reasoning: from 'A or B' and 'not A or C', conclude 'B or C'. Repeating it can demonstrate any conclusion that genuinely follows from what is known., unificationunification, n.: Finding values for the blanks in two logical patterns so that they become identical, for example matching 'parent(X, bob)' with 'parent(alice, Y)' by setting X to alice and Y to bob.