Prolog

Prolog expresses programs through facts and rules and answers queries by solving goals. A rule such as ancestor(X,Y) :- parent(X,Y). provides one way to establish a relationship. A recursive rule can search through intermediate parents. Unification matches a goal with a rule head and propagates bindings; backtracking explores alternative matches when a branch fails or another answer is requested.^[ref]

The logical core is associated with Horn clauses and SLD resolution, but clause order and goal order also determine a conventional Prolog program's search behavior. A logically valid recursive specification can loop before reaching an available answer. Predicates with input/output effects and control operations add further operational behavior. Arithmetic evaluation is also distinct from term matching: X = 1+2 builds a term, whereas X is 1+2 evaluates arithmetic in the usual Prolog interface.

SLD resolution is a goal-directed inference rule for definite first-order Horn clauses. It selects an atom from the current goal, matches it with a suitably renamed clause head using a most general unifier, and replaces it by that clause's body, applying the same first-order substitution throughout the goal. Reaching the empty goal supplies a successful derivation.^[ref]

For example, the rule ancestor(X,Y) :- parent(X,Y) reduces the query ancestor(ada,Y) to parent(ada,Y). Matching the fact parent(ada,ben) then gives Y=ben. Alternative matching clauses create a search tree. Prolog normally selects the leftmost goal and searches clauses in order with backtracking; a recursive branch can therefore run indefinitely before another branch's valid answer is reached. The logical inference rule and the strategy traversing its alternatives are separate choices.