Prolog

Prolog. Prolog is a logic programming language associated with artificial intelligence and computational linguistics. It was created in the early 1970s by Alain Colmerauer and Philippe Roussel at the University of Aix-Marseille, with key contributions from Robert Kowalski. The language is based on the formal foundations of first-order logic, specifically Horn clauses, and its name is derived from the French phrase "Programmation en Logique."

Overview

Prolog's core execution mechanism is a theorem prover that uses a specific form of resolution (logic) known as SLD resolution. A Prolog program consists of a database of facts and rules, which the interpreter uses to answer queries through a built-in backtracking search algorithm. This design makes it fundamentally different from imperative programming languages like C (programming language) or object-oriented programming languages like Java (programming language). Its development was heavily influenced by earlier work on automated theorem proving, such as the Resolution principle developed by John Alan Robinson. The language gained significant attention through its adoption in the Fifth Generation Computer Systems project initiated by Japan's Ministry of International Trade and Industry.

Syntax and semantics

The basic syntactic constructs of Prolog are terms, which include atoms, numbers, variables, and compound terms. A program is composed of clauses, which are either facts (unconditional truths) or rules (conditional statements using the neck operator, `:-`). The semantics are defined by the closed-world assumption, where anything not provable from the program is considered false. Unification, a pattern-matching process central to execution, is used to match query variables with program terms. Control flow is managed implicitly through the order of clauses and the search strategy of the interpreter, though programmers can exert control using predicates like the cut operator (`!`). The theoretical underpinnings are deeply connected to the model theory of logic and the work of logicians like Alfred Tarski.

Programming examples

A classic example is a knowledge base about family relationships. Facts might state `parent(ann, bob).` and `parent(bob, carol).` A recursive rule like `ancestor(X, Y) :- parent(X, Y).` and `ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).` defines the ancestor relation. Querying `?- ancestor(ann, carol).` would return true. Another famous Prolog program is a solver for the Eight queens puzzle, elegantly demonstrating declarative problem-solving. The language is also well-suited for natural language processing tasks; early systems like Chat-80 used Prolog to answer questions posed in English about geography. List processing, a staple of symbolic computation, uses a syntax derived from Lisp (programming language), as in `[Head | Tail]`.

Implementations and variants

The first implementation, Prolog I, was developed at the University of Aix-Marseille. A highly influential version, Edinburgh Prolog, was created at the University of Edinburgh by David H. D. Warren and Fernando Pereira; its Warren Abstract Machine became a standard compilation target. Modern, high-performance implementations include SWI-Prolog, developed at the University of Amsterdam, and GNU Prolog. Variants have extended the language's core paradigm: Constraint logic programming systems like CLP(R) integrate constraints over real numbers, while Concurrent Prolog and its successor Guarded Horn Clauses introduced concurrency. Other notable dialects include Visual Prolog (formerly Turbo Prolog) and ISO/IEC 13211-1, which defines a standard for the language.

Applications

Historically, Prolog has been extensively used in expert systems and knowledge representation, forming the core of systems like APES and POPLOG. In computational linguistics, it was central to projects like the SRI International-developed Core Language Engine. It remains a teaching tool for concepts in logic and symbolic computation at institutions like the Massachusetts Institute of Technology. Practical applications include type inference in compilers, ontological reasoning for the Semantic Web, and protocol verification in hardware description languages. It is also used in bioinformatics for genome analysis and in the development of adventure games, such as the classic Colossal Cave Adventure.

Category:Logic programming languages Category:Programming languages created in 1972 Category:Artificial intelligence