| Paradigm: | Logic |
| Designers: | Alain Colmerauer |
| Latest Release Version: | Part 1: General core-Edition 1 Part 2: Modules-Edition 1 |
| Typing: | Untyped (its single data type is "term") |
| Implementations: | Amzi! Prolog, B-Prolog, Ciao, ECLiPSe, GNU Prolog, LPA Prolog, Poplog, P#, Quintus Prolog, Scryer Prolog, SICStus, Strawberry, SWI-Prolog, Tau Prolog, tuProlog, WIN-PROLOG XSB, YAP. |
| Dialects: | ISO Prolog, Edinburgh Prolog |
| Influenced By: | Planner |
| Influenced: | CHR, Clojure, Datalog, Erlang, Epilog, KL0, KL1, Logtalk, Mercury, Oz, Strand, Visual Prolog |
| File Ext: | .pl, .pro, .P |
| Website: | Part 1: Part 2: |
| Wikibooks: | Prolog |
Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving and computational linguistics.[1] [2] [3]
Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily as a declarative programming language: the program is a set of facts and rules, which define relations. A computation is initiated by running a query over the program.
Prolog was one of the first logic programming languages[4] and remains the most popular such language today, with several free and commercial implementations available. The language has been used for theorem proving,[5] expert systems,[6] term rewriting,[7] type systems,[8] and automated planning,[9] as well as its original intended field of use, natural language processing.[10] [11]
Prolog is a Turing-complete, general-purpose programming language, which is well-suited for intelligent knowledge-processing applications.
See main article: Prolog syntax and semantics. In Prolog, program logic is expressed in terms of relations, and a computation is initiated by running a query over these relations. Relations and queries are constructed using Prolog's single data type, the term.[12] Relations are defined by clauses. Given a query, the Prolog engine attempts to find a resolution refutation of the negated query. If the negated query can be refuted, i.e., an instantiation for all free variables is found that makes the union of clauses and the singleton set consisting of the negated query false, it follows that the original query, with the found instantiation applied, is a logical consequence of the program. This makes Prolog (and other logic programming languages) particularly useful for database, symbolic mathematics, and language parsing applications. Because Prolog allows impure predicates, checking the truth value of certain special predicates may have some deliberate side effect, such as printing a value to the screen. Because of this, the programmer is permitted to use some amount of conventional imperative programming when the logical paradigm is inconvenient. It has a purely logical subset, called "pure Prolog", as well as a number of extralogical features.
Prolog's single data type is the term. Terms are either atoms, numbers, variables or compound terms.[13]
x, red, 'Taco', 'some atom', and 'p(a)'.person_friends(zelda,[tom,jim]).Special cases of compound terms:
[]. For example, [1,2,3,4] or [red,green,blue].double_quotes. For example, "to be, or not to be".[14]Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to Horn clauses. Two types of Horn clauses are used to define Prolog programs: rules and facts. A rule is of the form
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:
which is equivalent to the rule:
The built-in predicate true/0 is always true.
Given the above fact, one can ask:
is socrates a human?
what things are humans?
Clauses with bodies are called rules. An example of a rule is:
If we add that rule and ask what things are mortals?
A predicate (or procedure definition) is a collection of clauses whose heads have the same name and arity. We use the notation name/arity to refer to predicates. A logic program is a set of predicates. For example, the following Prolog program, which defines some family relations, has four predicates:
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).
Predicate father_child/2 has three clauses, all of which are facts, and predicate parent_child/2 has two clauses, both are rules.
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.
Iterative algorithms can be implemented by means of recursive predicates.[15]
Consider the parent_child/2 predicate defined in the family relation program above. The following Prolog program defines the ancestor relation:ancestor/2 in the body of the second clause).
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, given the family relation program defined above, the following query will be evaluated to true:
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:
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.
The built-in Prolog predicate \+/1 provides negation as failure, which allows for non-monotonic reasoning. The goal \+ illegal(X) in the rule
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.
In Prolog, loading code is referred to as consulting. Prolog can be used interactively by entering queries at the Prolog prompt ?-. If there is no solution, Prolog writes no. If a solution exists then it is printed. If there are multiple solutions to the query, then these can be requested by entering a semi-colon ;. There are guidelines on good programming practice to improve code efficiency, readability and maintainability.[16]
Here follow some example programs written in Prolog.
Example of a basic query in a couple of popular Prolog dialects:
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:
or equivalently using DCG notation:
The quicksort sorting algorithm, relating a list to its sorted version:
quicksort([]) --> [].quicksort([X|Xs]) -->, quicksort(Smaller), [X], quicksort(Bigger).
A design pattern is a general reusable solution to a commonly occurring problem in software design. Some design patterns in Prolog are skeletons, techniques,[17] [18] cliches,[19] program schemata,[20] logic description schemata,[21] and higher-order programming.[22]
See main article: Higher-order logic and Higher-order programming. A higher-order predicate is a predicate that takes one or more other predicates as arguments. Although support for higher-order programming takes Prolog outside the domain of first-order logic, which does not allow quantification over predicates,[23] ISO Prolog now has some built-in higher-order predicates such as call/1, call/2, call/3, findall/3, setof/3, and bagof/3. Furthermore, since arbitrary Prolog goals can be constructed and evaluated at run-time, it is easy to write higher-order predicates like maplist/2, which applies an arbitrary predicate to each member of a given list, and sublist/3, which filters elements that satisfy a given predicate, also allowing for currying.[22]
To convert solutions from temporal representation (answer substitutions on backtracking) to spatial representation (terms), Prolog has various all-solutions predicates that collect all answer substitutions of a given query in a list. This can be used for list comprehension. For example, perfect numbers equal the sum of their proper divisors:
As another example, the predicate maplist applies a predicate P to all corresponding positions in a pair of lists:
When P is a predicate that for all X, P(X,Y) unifies Y with a single unique value, maplist(P, Xs, Ys) is equivalent to applying the map function in functional programming as Ys = map(Function, Xs).
Higher-order programming style in Prolog was pioneered in HiLog and λProlog.
For programming in the large, Prolog provides a module system, which is in the ISO Standard.[24] However, while most Prolog systems support structuring the code into modules, virtually no implementation adheres to the modules part of the ISO standard. Instead, most Prolog systems have decided to support as de-facto module standard the Quintus/SICStus module system. However, further convenience predicates concerning modules are provided by some implementations only and often have subtle differences in their semantics.
Some systems chose to implement module concepts as source-to-source compilation into base ISO Prolog, as is the case of Logtalk. GNU Prolog initially diverted from ISO modules, opting instead for Contextual Logic Programming, in which unit (module) loading and unloading can be made dynamically. Ciao designed a strict module system that, while being basically compatible with the de-facto standard used by other Prolog systems, is amenable to precise static analysis, supports term hiding, and facilitates programming in the large. XSB takes a different approach and offers an atom-based module system. The latter two Prolog systems allow controlling the visibility of terms in addition to that of predicates.
See main article: Definite clause grammar. There is a special notation called definite clause grammars (DCGs). A rule defined via -->/2 instead of :-/2 is expanded by the preprocessor (expand_term/2, a facility analogous to macros in other languages) according to a few straightforward rewriting rules, resulting in ordinary Prolog clauses. Most notably, the rewriting equips the predicate with two additional arguments, which can be used to implicitly thread state around, analogous to monads in other languages. DCGs are often used to write parsers or list generators, as they also provide a convenient interface to difference lists.
Prolog is a homoiconic language and provides many facilities for reflective programming (reflection). Its implicit execution strategy makes it possible to write a concise meta-circular evaluator (also called meta-interpreter) for pure Prolog code:
true represents an empty conjunction, and clause(Head, Body) unifies with clauses in the database of the form Head :- Body.
Since Prolog programs are themselves sequences of Prolog terms (:-/2 is an infix operator) that are easily read and inspected using built-in mechanisms (like read/1), it is possible to write customized interpreters that augment Prolog with domain-specific features. For example, Sterling and Shapiro present a meta-interpreter that performs reasoning with uncertainty, reproduced here with slight modifications:[25]
This interpreter uses a table of built-in Prolog predicates of the form[25]
and clauses represented as clause_cf(Head, Body, Certainty). Given those, it can be called as solve(Goal, Certainty) to execute Goal and obtain a measure of certainty about the result.
Pure Prolog is based on a subset of first-order predicate logic, Horn clauses, which is Turing-complete. Turing completeness of Prolog can be shown by using it to simulate a Turing machine:
perform(qf, Ls, Ls, Rs, Rs) :- !.perform(Q0, Ls0, Ls, Rs0, Rs) :- symbol(Rs0, Sym, RsRest), once(rule(Q0, Sym, Q1, NewSym, Action)), action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1), perform(Q1, Ls1, Ls, Rs1, Rs).
symbol([], b, []).symbol([Sym|Rs], Sym, Rs).
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).action(stay, Ls, Ls, Rs, Rs).action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
left([], [], Rs0, [b|Rs0]).left([L|Ls], Ls, Rs, [L|Rs]).
A simple example Turing machine is specified by the facts:
This machine performs incrementation by one of a number in unary encoding: It loops over any number of "1" cells and appends an additional "1" at the end. Example query and result:
This illustrates how any computation can be expressed declaratively as a sequence of state transitions, implemented in Prolog as a relation between successive states of interest.
The International Organization for Standardization (ISO) Prolog technical standard consists of two parts. ISO/IEC 13211-1,[26] [27] 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,[28] Cor.2:2012,[29] and Cor.3:2017.[30] ISO/IEC 13211-2,[26] published in 2000, adds support for modules to the standard. The standard is maintained by the ISO/IEC JTC1/SC22/WG17[31] working group. ANSI X3J17 is the US Technical Advisory Group for the standard.[32]
For efficiency, Prolog code is typically compiled to abstract machine code, often influenced by the register-based Warren Abstract Machine (WAM) instruction set.[33] 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.[34] 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.
See main article: Term indexing. 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.[35] 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.[36] [37]
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.
See main article: Tabled logic programming. 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:[38] [39]
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.[40]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.[41] [42] [43] Furthermore, Prolog has a number of properties that may allow speed-up through parallel execution.[44] A more recent approach has been to compile restricted Prolog programs to a field programmable gate array.[45] 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.[46]
Although Prolog is widely used in research and education,[47] Prolog and other logic programming languages have not had a significant impact on the computer industry in general.[48] Most applications are small by industrial standards, with few exceeding 100,000 lines of code.[48] [49] Programming in the large is considered to be complex because not all Prolog compilers support modules, and there are compatibility problems between the module systems of the major Prolog compilers. Portability of Prolog code across implementations has also been a problem, but developments since 2007 have meant: "the portability within the family of Edinburgh/Quintus derived Prolog implementations is good enough to allow for maintaining portable real-world applications."[50]
Software developed in Prolog has been criticised for having a high performance penalty compared to conventional programming languages. In particular, Prolog's non-deterministic evaluation strategy can be problematic when programming deterministic computations, or when even using "don't care non-determinism" (where a single choice is made instead of backtracking over all possibilities). Cuts and other language constructs may have to be used to achieve desirable performance, destroying one of Prolog's main attractions, the ability to run programs "backwards and forwards".[51]
Prolog is not purely declarative: because of constructs like the cut operator, a procedural reading of a Prolog program is needed to understand it. The order of clauses in a Prolog program is significant, as the execution strategy of the language depends on it.[52] Other logic programming languages, such as Datalog, are truly declarative but restrict the language. As a result, many practical Prolog programs are written to conform to Prolog's depth-first search order, rather than as purely declarative logic programs.[51]
Various implementations have been developed from Prolog to extend logic programming abilities in many directions. These include types, modes, constraint logic programming (CLP), object-oriented logic programming (OOLP), concurrency, linear logic (LLP), functional and higher-order logic programming abilities, plus interoperability with knowledge bases:
Prolog is an untyped language. Attempts to introduce and extend Prolog with types began in the 1980s,[53] [54] and continue .[55] Type information is useful not only for type safety but also for reasoning about Prolog programs.[56]
| Mode specifier | Interpretation | |
|---|---|---|
+ | nonvar on entry | |
- | var on entry | |
? | Not specified |
Constraint logic programming extends Prolog to include concepts from constraint satisfaction.[61] [62] 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[63] 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,[64] Visual Prolog, WIN-PROLOG, and B-Prolog.
Prolog-MPI is an open-source SWI-Prolog extension for distributed computing over the Message Passing Interface.[65] Also there are various concurrent Prolog programming languages.[66]
Some Prolog implementations, notably Visual Prolog, SWI-Prolog and Ciao, support server-side web programming with support for web protocols, HTML and XML.[67] There are also extensions to support semantic web formats such as Resource Description Framework (RDF) and Web Ontology Language (OWL).[68] Prolog has also been suggested as a client-side language.[69] In addition, Visual Prolog supports JSON-RPC and Websockets.
Cedar 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.
Frameworks exist which can bridge between Prolog and other languages:
The name Prolog was chosen by Philippe Roussel, at the suggestion of his wife, as an abbreviation for French: programmation en logique (French for programming in logic).[71] It was created around 1972 by Alain Colmerauer with Philippe Roussel, based on Robert Kowalski's procedural interpretation of Horn clauses. It was motivated in part by the desire to reconcile the use of logic as a declarative knowledge representation language with the procedural representation of knowledge that was popular in North America in the late 1960s and early 1970s. According to Robert Kowalski, the first Prolog system was developed in 1972 by Colmerauer and Phillipe Roussel.[72] [73] [74] The first implementation of Prolog was an interpreter written in Fortran by Gerard Battani and Henri Meloni. David H. D. Warren took this interpreter to the University of Edinburgh, and there implemented an alternative front-end, which came to define the "Edinburgh Prolog" syntax used by most modern implementations. Warren also implemented the first compiler for Prolog, creating the influential DEC-10 Prolog in collaboration with Fernando Pereira. Warren later generalised the ideas behind DEC-10 Prolog, to create the Warren Abstract Machine.
European AI researchers favored Prolog while Americans favored Lisp, reportedly causing many nationalistic debates on the merits of the languages.[75] Much of the modern development of Prolog came from the impetus of the Fifth Generation Computer Systems project (FGCS), which developed a variant of Prolog named Kernel Language for its first operating system.
Pure Prolog was originally restricted to the use of a resolution theorem prover with Horn clauses of the form:
H :- B1, ..., Bn.
The application of the theorem-prover treats such clauses as procedures:
to show/solve H, show/solve B1 and ... and Bn.
Pure Prolog was soon extended, however, to include negation as failure, in which negative conditions of the form not(Bi) are shown by trying and failing to solve the corresponding positive conditions Bi.
Subsequent extensions of Prolog by the original team introduced constraint logic programming abilities into the implementations.
Prolog has been used in Watson. Watson uses IBM's DeepQA software and the Apache UIMA (Unstructured Information Management Architecture) framework. The system was written in various languages, including Java, C++, and Prolog, and runs on the SUSE Linux Enterprise Server 11 operating system using Apache Hadoop framework to provide distributed computing. Prolog is used for pattern matching over natural language parse trees. The developers have stated: "We required a language in which we could conveniently express pattern matching rules over the parse trees and other annotations (such as named entity recognition results), and a technology that could execute these rules very efficiently. We found that Prolog was the ideal choice for the language due to its simplicity and expressiveness."[11] Prolog is being used in the Low-Code Development Platform GeneXus, which is focused around AI. Open source graph database TerminusDB is implemented in Prolog. TerminusDB is designed for collaboratively building and curating knowledge graphs.