Prolog

Prolog's single data type is the term. Terms are either atoms, numbers, variables or compound terms.

• An atom is a general-purpose name with no inherent meaning. Examples of atoms include x, red, 'Taco', and 'some atom'.
• Numbers can be floats or integers. ISO standard compatible Prolog systems can check the Prolog flag "bounded". Most of the major Prolog systems support arbitrary length integer numbers.
• Variables are denoted by a string consisting of letters, numbers and underscore characters, and beginning with an upper-case letter or underscore. Variables closely resemble variables in logic in that they are placeholders for arbitrary terms.
• A compound term is composed of an atom called a "functor" and a number of "arguments", which are again terms. Compound terms are ordinarily written as a functor followed by a comma-separated list of argument terms, which is contained in parentheses. The number of arguments is called the term's arity. An atom can be regarded as a compound term with arity zero. An example of a compound term is person_friends(zelda,[tom,jim]).

Special cases of compound terms:

• A List is an ordered collection of terms. It is denoted by square brackets with the terms separated by commas, or in the case of the empty list, by []. For example, [1,2,3] or [red,green,blue].
• Strings: A sequence of characters surrounded by quotes is equivalent to either a list of (numeric) character codes, a list of characters (atoms of length 1), or an atom depending on the value of the Prolog flag double_quotes. For example, "to be, or not to be".[16]

ISO Prolog provides the atom/1, number/1, integer/1, and float/1 predicates for type-checking.[17]

Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to Horn clauses. There are two types of clauses: facts and rules. A rule is of the form

Head :- Body.

and is read as "Head is true if Body is true". A rule's body consists of calls to predicates, which are called the rule's goals. The built-in logical operator ,/2 (meaning an arity 2 operator with name ,) denotes conjunction of goals, and ;/2 denotes disjunction. Conjunctions and disjunctions can only appear in the body, not in the head of a rule.

Clauses with empty bodies are called facts. An example of a fact is:

cat(tom).

which is equivalent to the rule:

cat(tom) :- true.

The built-in predicate true/0 is always true.

Given the above fact, one can ask:

is tom a cat?

 ?- cat(tom).
 Yes

what things are cats?

 ?- cat(X).
 X = tom

Clauses with bodies are called rules. An example of a rule is:

animal(X) :- cat(X).

If we add that rule and ask what things are animals?

 ?- animal(X).
 X = tom

Due to the relational nature of many built-in predicates, they can typically be used in several directions. For example, length/2 can be used to determine the length of a list (length(List, L), given a list List), and to generate a list skeleton of a given length (length(X, 5)), and to generate both list skeletons and their lengths together (length(X, L)). Similarly, append/3 can be used both to append two lists (append(ListA, ListB, X) given lists ListA and ListB), and to split a given list into parts (append(X, Y, List), given a list List). For this reason, a comparatively small set of library predicates suffices for many Prolog programs.

As a general purpose language, Prolog also provides various built-in predicates to perform routine activities like input/output, using graphics and otherwise communicating with the operating system. These predicates are not given a relational meaning and are only useful for the side-effects they exhibit on the system. For example, the predicate write/1 displays a term on the screen.

Execution of a Prolog program is initiated by the user's posting of a single goal, called the query. Logically, the Prolog engine tries to find a resolution refutation of the negated query. The resolution method used by Prolog is called SLD resolution. If the negated query can be refuted, it follows that the query, with the appropriate variable bindings in place, is a logical consequence of the program. In that case, all generated variable bindings are reported to the user, and the query is said to have succeeded. Operationally, Prolog's execution strategy can be thought of as a generalization of function calls in other languages, one difference being that multiple clause heads can match a given call. In that case, the system creates a choice-point, unifies the goal with the clause head of the first alternative, and continues with the goals of that first alternative. If any goal fails in the course of executing the program, all variable bindings that were made since the most recent choice-point was created are undone, and execution continues with the next alternative of that choice-point. This execution strategy is called chronological backtracking. For example:

mother_child(trude, sally).
 
father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).
 
sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).
 
parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

This results in the following query being evaluated as true:

 ?- sibling(sally, erica).
 Yes

This is obtained as follows: Initially, the only matching clause-head for the query sibling(sally, erica) is the first one, so proving the query is equivalent to proving the body of that clause with the appropriate variable bindings in place, i.e., the conjunction (parent_child(Z,sally), parent_child(Z,erica)). The next goal to be proved is the leftmost one of this conjunction, i.e., parent_child(Z, sally). Two clause heads match this goal. The system creates a choice-point and tries the first alternative, whose body is father_child(Z, sally). This goal can be proved using the fact father_child(tom, sally), so the binding Z = tom is generated, and the next goal to be proved is the second part of the above conjunction: parent_child(tom, erica). Again, this can be proved by the corresponding fact. Since all goals could be proved, the query succeeds. Since the query contained no variables, no bindings are reported to the user. A query with variables, like:

?- father_child(Father, Child).

enumerates all valid answers on backtracking.

Notice that with the code as stated above, the query ?- sibling(sally, sally). also succeeds. One would insert additional goals to describe the relevant restrictions, if desired.

Iterative algorithms can be implemented by means of recursive predicates.[18]

The built-in Prolog predicate \+/1 provides negation as failure, which allows for non-monotonic reasoning. The goal \+ illegal(X) in the rule

legal(X) :- \+ illegal(X).

is evaluated as follows: Prolog attempts to prove illegal(X). If a proof for that goal can be found, the original goal (i.e., \+ illegal(X)) fails. If no proof can be found, the original goal succeeds. Therefore, the \+/1 prefix operator is called the "not provable" operator, since the query ?- \+ Goal. succeeds if Goal is not provable. This kind of negation is sound if its argument is "ground" (i.e. contains no variables). Soundness is lost if the argument contains variables and the proof procedure is complete. In particular, the query ?- legal(X). now cannot be used to enumerate all things that are legal.

Example of a basic query in a couple of popular Prolog dialects:

?- write('Hello World!'), nl.
Hello World!
true.

?-

| ?- write('Hello World!'), nl.
Hello World!

yes
| ?-

This comparison shows the prompt ("?-" vs "| ?-") and resolution status ("true." vs "yes", "false." vs "no") can differ from one Prolog implementation to another.

Any computation can be expressed declaratively as a sequence of state transitions. As an example, an optimizing compiler with three optimization passes could be implemented as a relation between an initial program and its optimized form:

program_optimized(Prog0, Prog) :-
    optimization_pass_1(Prog0, Prog1),
    optimization_pass_2(Prog1, Prog2),
    optimization_pass_3(Prog2, Prog).

or equivalently using DCG notation:

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

The quicksort sorting algorithm, relating a list to its sorted version:

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).
 
quicksort([])     --> [].
quicksort([X|Xs]) -->
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

The International Organization for Standardization (ISO) Prolog technical standard consists of two parts. ISO/IEC 13211-1,[27][31] published in 1995, aims to standardize the existing practices of the many implementations of the core elements of Prolog. It has clarified aspects of the language that were previously ambiguous and leads to portable programs. There are three corrigenda: Cor.1:2007,[32] Cor.2:2012,[33] and Cor.3:2017.[34] ISO/IEC 13211-2,[27] published in 2000, adds support for modules to the standard. The standard is maintained by the ISO/IEC JTC1/SC22/WG17[35] working group. ANSI X3J17 is the US Technical Advisory Group for the standard.[36]

For efficiency, Prolog code is typically compiled to abstract machine code, often influenced by the register-based Warren Abstract Machine (WAM) instruction set.[37] Some implementations employ abstract interpretation to derive type and mode information of predicates at compile time, or compile to real machine code for high performance.[38] Devising efficient implementation methods for Prolog code is a field of active research in the logic programming community, and various other execution methods are employed in some implementations. These include clause binarization and stack-based virtual machines.

Prolog systems typically implement a well-known optimization method called tail call optimization (TCO) for deterministic predicates exhibiting tail recursion or, more generally, tail calls: A clause's stack frame is discarded before performing a call in a tail position. Therefore, deterministic tail-recursive predicates are executed with constant stack space, like loops in other languages.

Finding clauses that are unifiable with a term in a query is linear in the number of clauses. Term indexing uses a data structure that enables sub-linear-time lookups.[39] Indexing only affects program performance, it does not affect semantics. Most Prologs only use indexing on the first term, as indexing on all terms is expensive, but techniques based on field-encoded words or superimposed codewords provide fast indexing across the full query and head.[40][41]

Some Prolog systems, such as WIN-PROLOG and SWI-Prolog, now implement hashing to help handle large datasets more efficiently. This tends to yield very large performance gains when working with large corpora such as WordNet.

Some Prolog systems, (B-Prolog, XSB, SWI-Prolog, YAP, and Ciao), implement a memoization method called tabling, which frees the user from manually storing intermediate results. Tabling is a space–time tradeoff; execution time can be reduced by using more memory to store intermediate results:[42][43]

Subgoals encountered in a query evaluation are maintained in a table, along with answers to these subgoals. If a subgoal is re-encountered, the evaluation reuses information from the table rather than re-performing resolution against program clauses.[44]

Tabling can be extended in various directions. It can support recursive predicates through SLG resolution or linear tabling. In a multi-threaded Prolog system tabling results could be kept private to a thread or shared among all threads. And in incremental tabling, tabling might react to changes.

During the Fifth Generation Computer Systems project, there were attempts to implement Prolog in hardware with the aim of achieving faster execution with dedicated architectures.[45][46][47] Furthermore, Prolog has a number of properties that may allow speed-up through parallel execution.[48] A more recent approach has been to compile restricted Prolog programs to a field programmable gate array.[49] However, rapid progress in general-purpose hardware has consistently overtaken more specialised architectures.

Sega implemented Prolog for use with the Sega AI Computer, released for the Japanese market in 1986. Prolog was used for reading natural language inputs, in the Japanese language, via a touch pad.[50]

Prolog is an untyped language. Attempts to introduce and extend Prolog with types began in the 1980s,[58][59] and continue as of 2008.[60] Type information is useful not only for type safety but also for reasoning about Prolog programs.[61]

The syntax of Prolog does not specify which arguments of a predicate are inputs and which are outputs.[62] However, this information is significant and it is recommended that it be included in the comments.[63] Modes provide valuable information when reasoning about Prolog programs[61] and can also be used to accelerate execution.[64]

Constraint logic programming extends Prolog to include concepts from constraint satisfaction.[65][66] A constraint logic program allows constraints in the body of clauses, such as: A(X,Y) :- X+Y>0. It is suited to large-scale combinatorial optimisation problems[67] and is thus useful for applications in industrial settings, such as automated time-tabling and production scheduling. Most Prolog systems ship with at least one constraint solver for finite domains, and often also with solvers for other domains like rational numbers.

Flora-2 is an object-oriented knowledge representation and reasoning system based on F-logic and incorporates HiLog, Transaction logic, and defeasible reasoning.

Logtalk is an object-oriented logic programming language that can use most Prolog implementations as a back-end compiler. As a multi-paradigm language, it includes support for both prototypes and classes.

Oblog is a small, portable, object-oriented extension to Prolog by Margaret McDougall of EdCAAD, University of Edinburgh.

Objlog was a frame-based language combining objects and Prolog II from CNRS, Marseille, France.

Prolog++ was developed by Logic Programming Associates and first released in 1989 for MS-DOS PCs. Support for other platforms was added, and a second version was released in 1995. A book about Prolog++ by Chris Moss was published by Addison-Wesley in 1994.

Visual Prolog is a multi-paradigm language with interfaces, classes, implementations and object expressions.

Prolog systems that provide a graphics library are SWI-Prolog,[68] Visual Prolog, WIN-PROLOG, and B-Prolog.

Prolog-MPI is an open-source SWI-Prolog extension for distributed computing over the Message Passing Interface.[69] Also there are various concurrent Prolog programming languages.[70]

Some Prolog implementations, notably Visual Prolog, SWI-Prolog and Ciao, support server-side web programming with support for web protocols, HTML and XML.[71] There are also extensions to support semantic web formats such as Resource Description Framework (RDF) and Web Ontology Language (OWL).[72][73] Prolog has also been suggested as a client-side language.[74] In addition, Visual Prolog supports JSON-RPC and Websockets.

Cedar Archived 2010-10-19 at the Wayback Machine is a free and basic Prolog interpreter. From version 4 and above Cedar has a FCA (Flash Cedar App) support. This provides a new platform to programming in Prolog through ActionScript.

• F-logic extends Prolog with frames/objects for knowledge representation.
• Transaction logic extends Prolog with a logical theory of state-changing update operators. It has both a model-theoretic and procedural semantics.
• OW Prolog has been created in order to answer Prolog's lack of graphics and interface.

• The Gödel language is a strongly typed implementation of concurrent constraint logic programming. It is built on SICStus Prolog.
• Visual Prolog, formerly named PDC Prolog and Turbo Prolog, is a strongly typed object-oriented dialect of Prolog, which is very different from standard Prolog. As Turbo Prolog, it was marketed by Borland, but is now developed and marketed by the Danish firm Prolog Development Center (PDC) that originally produced it.
• Datalog is a subset of Prolog. It is limited to relationships that may be stratified and does not allow compound terms. In contrast to Prolog, Datalog is not Turing-complete.
• Mercury is an offshoot of Prolog geared toward software engineering in the large with a static, polymorphic type system, as well as a mode and determinism system.
• GraphTalk is a proprietary implementation of Warren's Abstract Machine, with additional object-oriented properties.
• In some ways Prolog is a subset of Planner. The ideas in Planner were later further developed in the Scientific Community Metaphor.
• AgentSpeak is a variant of Prolog for programming agent behavior in multi-agent systems.
• Erlang began life with a Prolog-based implementation and maintains much of Prolog's unification-based syntax.
• Pilog is a declarative language built on top of PicoLisp, that has the semantics of Prolog, but uses the syntax of Lisp.