logic programming

artificial intelligence, programming, language A

declarative, relational style of programming based on

first-order logic. The original logic programming language

was Prolog. The concept is based on Horn clauses.

The programmer writes a "database" of "facts", e.g.

wet(water).

("water is wet") and "rules", e.g.

mortal(X) :- human(X).

("X is mortal is implied by X is human"). Facts and rules are

collectively known as "clauses".

The user supplies a "goal" which the system attempts to

prove using "resolution" or "backward chaining". This

involves matching the current goal against each fact or the

left hand side of each rule using "unification". If the

goal matches a fact, the goal succeeds; if it matches a rule

then the process recurses, taking each sub-goal on the right

hand side of the rule as the current goal. If all sub-goals

succeed then the rule succeeds.

Each time a possible clause is chosen, a "choice point" is

created on a stack. If subsequent resolution fails then

control eventually returns to the choice point and subsequent

clauses are tried. This is known as "backtracking".

Clauses may contain logic variables which take on any value

necessary to make the fact or the left hand side of the rule

match a goal. Unification binds these variables to the

corresponding subterms of the goal. Such bindings are

associated with the choice point at which the clause was

chosen and are undone when backtracking reaches that choice

point.

The user is informed of the success or failure of his first

goal and if it succeeds and contains variables he is told what

values of those variables caused it to succeed. He can then

ask for alternative solutions.

(1997-07-14)