Data types
Prolog is[]
, is also an atom. Other examples of atoms include x
, blue
, 'Taco'
, and 'some atom'
.
Numbers can be Floating point, floats or integers. Many Prolog implementations also provide unbounded integers and _
) denotes an anonymous variable and means "any term". Unlike other variables, the underscore does not represent the same value everywhere it occurs within a predicate definition.
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.
Examples of compound terms are truck_year('Mazda', 1986)
and 'Person_Friends'(zelda, om,jim
. Compound terms with functors that are declared as operators can be written in prefix or infix notation. For example, the terms -(z)
, +(a,b)
and =(X,Y)
can also be written as -z
, a+b
and X=Y
, respectively. Users can declare arbitrary functors as operators with different precedences to allow for domain-specific notations. The notation ''f/n'' is commonly used to denote a term with functor ''f'' and arity ''n''.
Special cases of compound terms:
* ''Lists'' are defined inductively: The atom []
is a list. A compound term with functor .
(dot) and arity 2, whose second argument is a list, is itself a list. There exists special syntax for denoting lists: .(A, B)
is equivalent to B/code>. For example, the list .(1, .(2, .(3, [])))
can also be written as [1 , [2 , [3 , [
, or even more compactly as [1,2,3]
.
* ''Strings'': A sequence of characters surrounded by quotes is equivalent to a list of (numeric) character codes, generally in the local character encoding
Character encoding is the process of assigning numbers to Graphics, graphical character (computing), characters, especially the written characters of Language, human language, allowing them to be Data storage, stored, Data communication, transmi ...
or Unicode
Unicode, formally The Unicode Standard,The formal version reference is is an information technology standard for the consistent encoding, representation, and handling of text expressed in most of the world's writing systems. The standard, wh ...
if the system supports Unicode.
Prolog programs
Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to Horn clauses, a Turing-complete
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any ...
subset of first-order predicate logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
. 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 predicate
Predicate or predication may refer to:
* Predicate (grammar), in linguistics
* Predication (philosophy)
* several closely related uses in mathematics and formal logic:
**Predicate (mathematical logic)
**Propositional function
**Finitary relation, o ...
,/2
(meaning a 2-arity operator with name ,
) denotes conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
of goals, and ;/2
denotes disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
. 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.
another example is:
X is 3+2.
and when you run it, the result will be
X=5
Yes.
The built-in predicate true/0
is always true.
Evaluation
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
Resolution(s) may refer to:
Common meanings
* Resolution (debate), the statement which is debated in policy debate
* Resolution (law), a written motion adopted by a deliberative body
* New Year's resolution, a commitment that an individual mak ...
refutation of the negated query. The resolution method used by Prolog is called SLD resolution SLD resolution (''Selective Linear Definite'' clause resolution) is the basic inference rule used in logic programming. It is a refinement of resolution, which is both sound and refutation complete for Horn clauses.
The SLD inference rule
Give ...
. 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
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it d ...
.
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.
Loops and recursion
Iterative algorithms can be implemented by means of recursive predicates. Prolog systems typically implement a well-known optimization technique called tail call
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
optimization (TCO) for deterministic predicates exhibiting tail recursion
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
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.
Cuts
A cut
Cut may refer to:
Common uses
* The act of cutting, the separation of an object into two through acutely-directed force
** A type of wound
** Cut (archaeology), a hole dug in the past
** Cut (clothing), the style or shape of a garment
** Cut (ea ...
(!
) inside a rule will prevent Prolog from backtracking any predicates behind the cut:
predicate(X) :- one(X), !, two(X).
will fail if the first-found value of X
for which one(X)
is true leads to two(X)
being false.
Anonymous variables
Anonymous variables _
are never bound to a value and can be used multiple times in a predicate.
For instance searching a list for a given value:
contains(V, _.
contains(V, T :- contains(V, T).
Negation
The built-in Prolog predicate \+/1
provides negation as failure Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive \mathrm~p (i.e. that ~p is assumed not to hold) from failure to derive ~p. Note that \mathrm ~p can be different from the statement \neg p ...
, 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 the 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
In physics, sound is a vibration that propagates as an acoustic wave, through a transmission medium such as a gas, liquid or solid.
In human physiology and psychology, sound is the ''reception'' of such waves and their ''perception'' b ...
if its argument is "ground" (i.e. contains no variables). Soundness is lost if the argument contains variables. In particular, the query ?- legal(X).
can now not be used to enumerate all things that are legal.
Semantics
Under a declarative reading, the order of rules, and of goals within rules, is irrelevant since logical disjunction and conjunction are commutative. Procedurally, however, it is often important to take into account Prolog's execution strategy, either for efficiency reasons, or due to the semantics of impure built-in predicates for which the order of evaluation matters.
Also, as Prolog interpreters try to unify clauses in the order they're provided, failing to give a correct ordering can lead to infinite recursion, as in:
predicate1(X) :-
predicate2(X,X).
predicate2(X,Y) :-
predicate1(X),
X \= Y.
Given this ordering, any query of the form
?- predicate1(atom).
will recur until the stack is exhausted. If, however, the last 3 lines were changed to:
predicate2(X,Y) :-
X \= Y,
predicate1(X).
the same query would lead to a No. outcome in a very short time.
Definite clause grammars
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 list differences.
Parser example
A larger example will show the potential of using Prolog in parsing
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from L ...
.
Given the sentence expressed in Backus–Naur form:
::=
::= ,
::= = ;
::= ,
::= ,
::= a , b
::= 0..9
::= + , - , *
This can be written in Prolog using DCGs, corresponding to a predictive parser with one token look-ahead:
sentence(S) --> statement(S0), sentence_r(S0, S).
sentence_r(S, S) --> [].
sentence_r(S0, seq(S0, S)) --> statement(S1), sentence_r(S1, S).
statement(assign(Id,E)) --> id(Id), [=], expression(E), [;].
expression(E) --> term(T), expression_r(T, E).
expression_r(E, E) --> [].
expression_r(E0, E) --> [+], term(T), expression_r(plus(E0,T), E).
expression_r(E0, E) --> [-], term(T), expression_r(minus(E0, T), E).
term(T) --> factor(F), term_r(F, T).
term_r(T, T) --> [].
term_r(T0, T) --> [*], factor(F), term_r(times(T0, F), T).
factor(id(ID)) --> id(ID).
factor(digit(D)) --> [D], { (number(D) ; var(D)), between(0, 9, D)}.
id(a) --> [a].
id(b) --> [b].
This code defines a relation between a sentence (given as a list of tokens) and its abstract syntax tree
In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each node of the tree denotes a construct occurr ...
(AST). Example query:
?- phrase(sentence(AST), ,=,1,+,3,*,b,;,b,=,0,;.
AST = seq(assign(a, plus(digit(1), times(digit(3), id(b)))), assign(b, digit(0))) ;
The AST is represented using Prolog terms and can be used to apply optimizations, to compile such expressions to machine-code, or to directly interpret such statements. As is typical for the relational nature of predicates, these definitions can be used both to parse and generate sentences, and also to check whether a given tree corresponds to a given list of tokens. Using iterative deepening for fair enumeration, each arbitrary but fixed sentence and its corresponding AST will be generated eventually:
?- length(Tokens, _), phrase(sentence(AST), Tokens).
Tokens = , =, a, (;) AST = assign(a, id(a)) ;
Tokens = , =, b, (;) AST = assign(a, id(b))
etc.
See also
* Comparison of Prolog implementations
The following Comparison of Prolog implementations provides a reference for the relative feature sets and performance of different implementations of the Prolog computer programming language.
Portability
There are Prolog implementations that are ...
References
Programming language syntax
Prolog programming language family