Thesyntax andsemantics ofProlog, aprogramming language, are the sets of rules that define how a Prolog program is written and how it is interpreted, respectively. The rules are laid out inISO standardISO/IEC 13211[1] although there are differences in theProlog implementations.
Prolog isdynamically typed. It has a singledata type, theterm, which has several subtypes:atoms,numbers,variables andcompound terms.
Anatom is a general-purpose name with no inherent meaning. It is composed of a sequence of characters that is parsed by the Prolog reader as a single unit. Atoms are usually bare words in Prolog code, written with no special syntax. However, atoms containing spaces or certain other special characters must be surrounded by single quotes. Atoms beginning with a capital letter must also be quoted, to distinguish them from variables. The empty list, written[], is also an atom. Other examples of atoms includex,blue,'Taco', and'some atom'.
Numbers can befloats orintegers. Many Prolog implementations also provide unbounded integers andrational 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 variable can become instantiated (bound to equal a specific term) viaunification. A single underscore (_) 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.
Acompound 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'sarity. An atom can be regarded as a compound term witharity zero.
Examples of compound terms aretruck_year('Mazda', 1986) and'Person_Friends'(zelda,[tom,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 andX=Y, respectively. Users can declare arbitrary functors as operators with different precedences to allow for domain-specific notations. The notationf/n is commonly used to denote a term with functorf and arityn.
Special cases of compound terms:
[] 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[A|B]. For example, the list.(1, .(2, .(3, []))) can also be written as[1 | [2 | [3 | []]]], or even more compactly as[1,2,3].Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted toHorn clauses, aTuring-complete subset of first-orderpredicate logic. 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'sgoals. The built-inpredicate,/2 (meaning a 2-arity operator with name,) denotesconjunction of goals, and;/2 denotesdisjunction. Conjunctions and disjunctions can only appear in the body, not in the head of a rule.
Clauses with empty bodies are calledfacts. An example of a fact is:
cat(tom).
which is equivalent to the rule:
cat(tom):-true.
another example is:
Xis3+2.
and when you run it, the result will be
X=5Yes.
The built-in predicatetrue/0 is always true.
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 aresolution refutation of the negated query. The resolution method used by Prolog is calledSLD resolution. If the negated query can be refuted, it follows that the query, with the appropriate variable bindings in place, is alogical 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 chronologicalbacktracking.
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 querysibling(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 isfather_child(Z, sally). This goal can be proved using the factfather_child(tom, sally), so the bindingZ = 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. Prolog systems typically implement a well-known optimization technique calledtail call optimization (TCO) for deterministic predicates exhibitingtail 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.
Acut (!) 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 ofX for whichone(X) is true leads totwo(X) being false.
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,[V|_]).contains(V,[_|T]):-contains(V,T).
The built-in Prolog predicate\+/1 providesnegation as failure, which allows fornon-monotonic reasoning. The goal\+ illegal(X) in the rule
legal(X):-\+illegal(X).
is evaluated as follows: Prolog attempts to prove theillegal(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 issound 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.
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.
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 tomonads in other languages. DCGs are often used to write parsers or list generators, as they also provide a convenient interface to list differences.
A larger example will show the potential of using Prolog inparsing.
Given the sentence expressed inBackus–Naur form:
<sentence>::=<stat_part><stat_part>::=<statement> |<stat_part><statement><statement>::=<id> =<expression> ;<expression>::=<operand> |<expression><operator><operand><operand>::=<id> |<digit><id>::= a | b<digit>::= 0..9<operator>::= + | - | *
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 itsabstract syntax tree (AST). Example query:
?-phrase(sentence(AST),[a,=,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. Usingiterative 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,=,a,(;)],AST=assign(a,id(a));Tokens=[a,=,b,(;)],AST=assign(a,id(b))etc.