Logic programming: the AI idea behind Prolog

Logic programming is a way of programming in which you write down what is true about a problem as facts and rules in formal logic, and the computer answers questions by reasoning from them. Wikipedia's article on logic programming calls it a programming, database and knowledge representation paradigm, and names Prolog, Answer Set Programming and Datalog as its major language families. This post explains how it works, how it grew out of an argument inside AI research in the 1970s, why it rose and fell with the hopes of the 1980s, and gives you a small rule base you can run by hand.

If you would like to think about where reasoning machines could lead inside a story, Contain ASI is a browser story strategy game for 1 to 4 players where you try to keep four fictional AI labs from crossing into recursive self-improvement before 2027.

What logic programming is

A logic program is a set of sentences in logical form that represent knowledge about some problem. Computation means applying logical reasoning to that knowledge to solve problems in the domain.

The sentences are written as clauses. A rule has a head and a body, written A :- B1, ..., Bn. and read as "A if B1 and ... and Bn". A rule with no body is a fact, written simply as A. A question, called a query or goal, looks like a body: ?- B1, ..., Bn.

In the simplest case, Horn clauses, every part is an atomic formula such as parent_child(X, Y): a predicate that names a relation, applied to terms that name things. Terms can be constants or variables, and variables start with a capital letter.

One program answers many kinds of question. In the article's family example, one grandparent rule can find a person's grandparents, their grandchildren, or check whether a given pair fits.

Where logic programming came from: an argument inside AI

Logic programming, with its syntax of facts and rules, can be traced back to debates in the late 1960s and early 1970s about declarative versus procedural representations of knowledge in artificial intelligence. Should a machine store what is true, or how to act?

• The declarative side worked at Stanford, around John McCarthy, Bertram Raphael and Cordell Green, and in Edinburgh, with John Alan Robinson, Pat Hayes and Robert Kowalski.
• The procedural side was mainly at MIT, led by Marvin Minsky and Seymour Papert. Carl Hewitt's Planner was its first language, and Terry Winograd used a subset of it, Micro-Planner, to build the natural language program SHRDLU.

Hayes and Kowalski tried to reconcile the two approaches.

The breakthrough came in Marseille. Alain Colmerauer was working on natural language understanding with logic. In the summer of 1971 he invited Kowalski, and together they found that clausal logic could represent grammars and that theorem provers could parse. In the summer of 1972 Kowalski developed the procedural interpretation of implications in clausal form, described in a 1973 memo published in 1974. Colmerauer and Philippe Roussel used it as the basis of Prolog, built in 1972; the first Prolog program was a French question answering system. In 1977 David H. D. Warren's compiler in Edinburgh made Prolog fast enough to compete with Lisp.

This is part of the larger story of symbolic AI, and of the split between careful logicians and hands-on builders described in neats and scruffies.

Algorithm = Logic + Control

One phrase sums up how logic programs run: "Algorithm = Logic + Control". The logic is what the program says is true. The control is the strategy used to search it. Different strategies applied to the same logic give different algorithms.

The two main strategies are backward reasoning, also called goal reduction or top-down reasoning, and forward reasoning, also called bottom-up reasoning. In Prolog's procedural reading, the rule A :- B1, ..., Bn means "to solve A, solve B1 and ... and solve Bn".

Prolog searches top-down and depth-first, trying subgoals in the order they are written and clauses in the order they appear. When a subgoal cannot be solved, it backtracks and tries the next matching clause. A special subgoal called cut, written !, stops backtracking; it can make programs faster but can also interfere with their logical meaning.

Strategy matters. For the Fibonacci numbers, backward reasoning solves the same subgoals again and again, and the work grows on the order of 2 to the power n. Forward reasoning builds the sequence from 0 and 1 with no repeats, in linear time. Prolog gets that effect through tabling: it stores solved subgoals and reuses them.

Negation as failure and the closed world

Pure Horn clauses cannot say "not". Real programs need negative conditions, so early Prolog systems used negation as failure: not B is taken to hold if the program fails to prove B.

Its logic stayed unclear until Keith Clark showed that, under certain natural conditions, negation as failure is a correct way of reasoning with the completion of a program. Roughly, the completion reads all the rules for a predicate as its full definition: A holds if and only if one of its bodies holds. Whatever the program cannot prove, it treats as false.

This is closed world reasoning, and it ties logic programming to a central problem of AI. The article's commonsense example uses a frame axiom: a fact that holds at one time keeps holding at the next unless some event ends it. That is the same puzzle covered in our post on the frame problem.

Try it: a small rule base on paper

Here is a tiny program of our own, written in the article's notation. Read it, then work out the answer by hand the way Prolog would.

• tested(alpha).
• tested(beta).
• flagged(beta).
• cleared(X) :- tested(X), not flagged(X).

Now ask ?- cleared(X). and follow these steps.

1. Reduce the goal. To prove cleared(X), prove tested(X), then not flagged(X).
2. Try the first fact. tested(alpha) matches, so X is alpha.
3. Check the negative condition. Try to prove flagged(alpha). No fact or rule gives it, so it fails, and not flagged(alpha) holds. Answer: X = alpha.
4. Ask for more. Backtrack to the next fact: tested(beta). Now flagged(beta) is a fact, so the negative condition fails. Beta gives no answer.
5. Change one line. Delete flagged(beta). and run it again. Both alpha and beta come out cleared.

Step 5 is the point to notice. Under negation as failure, a missing fact is read as false. The program did not learn that beta was safe; it only lost the record of a problem. Whenever you write rules that decide something, ask what the system will conclude about the things nobody wrote down.

The Fifth Generation project and what came after

Logic programming gained world attention in the 1980s, when Japan's Ministry of International Trade and Industry chose it for the Fifth Generation Computer Systems project. The project aimed to use logic programming to build advanced AI applications on massively parallel computers. It moved from Prolog to concurrent logic programming, whose committed choice feature interfered with its logical meaning, and its parallel machines failed to keep up with ordinary computers. The project missed its goals, and interest in both logic programming and AI fell into decline around the world.

The declarative strand kept going. Work on deductive databases became prominent around 1977, when Hervé Gallaire and Jack Minker organized a workshop on logic and databases in Toulouse; that field was later renamed Datalog. Constraint logic programming followed in the 1980s and Answer Set Programming in the 1990s. Inductive logic programming turned the idea around: it learns rules from positive and negative examples, as an approach to machine learning.

Logic programming and how people think

Some researchers use logic programs to model human reasoning. In his Introduction to Cognitive Science, Paul Thagard treats logic and rules as different ways to model thinking, and argues that rules such as "IF you want to go home for the weekend, and you have bus fare, THEN you can catch a bus" are simpler and more psychologically plausible than logic. The article replies that this goal reduction is backward reasoning on a logical conditional, so his view applies to logic programming too.

Keith Stenning and Michiel van Lambalgen, in Human Reasoning and Cognitive Science, use the non-monotonic character of logic programs to explain human performance on psychological tasks. For a wider view of how AI stores what it knows, see knowledge representation and reasoning.

Frequently asked questions

Is logic programming the same as Prolog?

No. Prolog is the best known logic programming language, but the paradigm also includes Datalog, Answer Set Programming, constraint logic programming and others. In Datalog and Answer Set Programming, programs have only a declarative reading.

Who invented logic programming?

No single person. Cordell Green made the first proposal to use clausal logic for programs, Robert Kowalski developed the procedural reading of clauses, and Alain Colmerauer and Philippe Roussel built Prolog on it in 1972.

Is logic programming used in machine learning?

Yes, in one branch. Inductive logic programming learns logic programs from background knowledge and positive and negative examples, producing general rules that fit the positive examples and exclude the negative ones.

Is Contain ASI a forecast of the future of AI?

No. Contain ASI is a game, and its page says all its labs, people and events are fictional. It is inspired by the AI 2027 scenario, and it is a story, not a forecast.

Get started with Contain ASI

Logic programming asks what a machine should conclude from the rules it is given, and what it assumes about everything left out. In Contain ASI you weigh choices like that as fiction: playing a researcher, research manager, CEO or government, you try for three years to keep four fictional AI labs from reaching recursive self-improvement before 2027. It runs in the browser and needs WebGL 2.

Play Contain ASI: a story strategy game for 1 to 4 players that runs in your browser. Its labs, people and events are all fictional.