Textbook of AI

Prolog (PROgrammation en LOGique), introduced by Alain Colmerauer and Philippe Roussel at Marseille in 1972, is the canonical logic-programming language. Programs are sets of Horn clauses:

• Facts: parent(tom, bob).
• Rules: grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Computation is SLD resolution, a restricted form of J. A. Robinson's 1965 resolution principle. To answer a query, Prolog searches for a derivation by backward chaining: try to unify the query with a fact or rule head, then recursively prove the rule's body. Backtracking explores alternative unifications.

Built-ins: arithmetic, list manipulation ([H|T]), I/O, the cut operator ! (commits to the current choice, prunes backtracking).

Major Prolog implementations: SWI-Prolog (open-source, widely-used), GNU Prolog, SICStus Prolog (commercial, fast).

Strengths:

• Concise expression of search problems, parsing, theorem proving.
• Built-in unification and backtracking.
• Bidirectional execution: a relation can be queried with any combination of bound and unbound variables.

Weaknesses:

• Performance: pure Prolog is slower than imperative implementations of the same algorithm (often 10-100× for many tasks).
• Closed-world assumption can be unintuitive.
• Cut and other extra-logical features break the pure declarative reading.
• Real-world tasks often need extensions (constraint solving, foreign function calls, OOP), pure Prolog is rarely sufficient.

Modern role: Prolog has largely been displaced by neural and statistical methods in mainstream AI but remains influential in:

• Computational linguistics: natural-language parsing, formal grammars.
• Theorem proving and formal verification.
• Education: a teaching language for declarative programming and logic.
• Niche applications: configuration, scheduling, expert systems, certain database query languages.

Japan's Fifth Generation Computer Systems Project (1981-1992) was largely organised around Prolog and parallel logic programming languages descended from it.