Editing Prolog (section)

== Syntax and semantics ==
{{Main|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''.<ref name=lloyd84>{{cite book |author=Lloyd, J. W. |title=Foundations of logic programming |publisher=Springer-Verlag |location=Berlin |year=1984 |isbn=978-3-540-13299-8}}</ref> Relations are defined by ''clauses''. Given a query, the Prolog engine attempts to find a [[resolution (logic)|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 [[Predicate (mathematical logic)|predicates]], checking the [[truth value]] of certain special predicates may have some deliberate [[side effect (computer science)|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.

=== Data types ===
Prolog's single [[data type]] is the ''term''. Terms are either ''[[symbol (programming)#Prolog|atom]]s'', ''numbers'', ''variables'' or ''compound terms''.<ref group=note>    The Prolog terminology differs from that of  [[First-order logic|logic]].
    A term of Prolog is (depending on the context) a [[Term (logic)|term]] or an [[atomic formula]] of logic.
    An atom in a standard logic terminology means an [[atomic formula]];  
    an atom of Prolog (depending on the context) is a constant, function
    symbol or predicate symbol of logic.
</ref>
* An '''atom''' is a symbol name starting with a lower case letter or guarded by quotes. Examples of atoms include <code>x</code>, <code>red</code>, <code>'Taco'</code>, <code>'some atom'</code>, and <code>'p(a)'</code>.
* '''Numbers''' can be [[floating-point arithmetic|floats]] or [[integer]]s.  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 <code>person_friends(zelda,[tom,jim])</code>.

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 <code>[]</code>. For example, <code>[1,2,3,4]</code> or <code>[red,green,blue]</code>.
* ''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 <code>double_quotes</code>. For example, <code>"to be, or not to be"</code>.<ref name="ISO 13211-1 6.3.7">ISO/IEC 13211-1:1995 Prolog, 6.3.7 Terms - double quoted list notation. [[International Organization for Standardization]], Geneva.</ref>

=== Rules and facts ===
Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to [[Horn clause]]s. Two types of Horn clauses are used to define Prolog programs: rules and facts. A rule is of the form
<syntaxhighlight lang="prolog">Head :- Body.</syntaxhighlight>
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]] <code>,/2</code> (meaning an arity 2 [[Operator (programming)|operator]] with name <code>,</code>) denotes [[logical conjunction|conjunction]] of goals, and <code>;/2</code> denotes [[logical disjunction|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:
<syntaxhighlight lang="prolog">human(socrates).</syntaxhighlight>
which is equivalent to the rule:
<syntaxhighlight lang="prolog">human(socrates) :- true.</syntaxhighlight>

The built-in predicate <code>true/0</code> is always true.

Given the above fact, one can ask:

''is socrates a human?''

<syntaxhighlight lang="prolog">
 ?- human(socrates).
 Yes
</syntaxhighlight>

''what things are humans?''

<syntaxhighlight lang="prolog">
 ?- human(X).
 X = socrates
</syntaxhighlight>

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

<syntaxhighlight lang="prolog">mortal(X) :- human(X).</syntaxhighlight>

If we add that rule and ask ''what things are mortals?''

<syntaxhighlight lang="prolog">
 ?- mortal(X).
 X = socrates
</syntaxhighlight>

=== Predicates and programs ===

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: <syntaxhighlight lang="prolog">
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), not(X = Y).

parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).
</syntaxhighlight>

Predicate <code>father_child/2</code> has three clauses, all of which are facts, and predicate <code>parent_child/2</code> 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, <code>length/2</code> can be used to determine the length of a list (<code>length(List, L)</code>, given a list <code>List</code>), and to generate a list skeleton of a given length (<code>length(X, 5)</code>), and to generate both list skeletons and their lengths together (<code>length(X, L)</code>). Similarly, <code>append/3</code> can be used both to append two lists (<code>append(ListA, ListB, X)</code> given lists <code>ListA</code> and <code>ListB</code>), and to split a given list into parts (<code>append(X, Y, List)</code>, given a list <code>List</code>). 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 <code>write/1</code> displays a term on the screen.

=== Loops and recursion ===
Iterative algorithms can be implemented by means of recursive predicates.<ref>{{cite book |last=Carlsson |first=Mats |url=https://books.google.com/books?id=dZimAwAAQBAJ&q=prolog%20failure%20driven%20loop%20%22iteration%22&pg=PA148 |title=SICStus Prolog User's Manual 4.3: Core reference documentation |date=27 May 2014 |publisher=BoD – Books on Demand |isbn=978-3-7357-3744-1 |via=Google Books}}</ref>

Consider the <code>parent_child/2</code> predicate defined in the family relation program above. The following Prolog program defines the ''ancestor'' relation:<syntaxhighlight lang="prolog">
ancestor(X, Y) :- parent_child(X, Y).
ancestor(X, Y) :- parent_child(X, Z), ancestor(Z, Y).
</syntaxhighlight>It expresses that X is an ancestor of Y if X is parent of Y or X is parent of an ancestor of Y.  It is recursive because it is defined in terms of itself (there is a call to predicate <code>ancestor/2</code> in the body of the second clause).   

=== Execution ===

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 (logic)|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, [[unification (computer science)|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:
<syntaxhighlight lang="prolog">
 ?- sibling(sally, erica).
 Yes
</syntaxhighlight>

This is obtained as follows: Initially, the only matching clause-head for the query <code>sibling(sally, erica)</code> 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 <code>(parent_child(Z,sally), parent_child(Z,erica))</code>. The next goal to be proved is the leftmost one of this conjunction, i.e., <code>parent_child(Z, sally)</code>. Two clause heads match this goal. The system creates a choice-point and tries the first alternative, whose body is <code>father_child(Z, sally)</code>. This goal can be proved using the fact <code>father_child(tom, sally)</code>, so the binding <code>Z = tom</code> is generated, and the next goal to be proved is the second part of the above conjunction: <code>parent_child(tom, erica)</code>. 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:
<syntaxhighlight lang="prolog">?- father_child(Father, Child).</syntaxhighlight>

enumerates all valid answers on backtracking.

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

=== Negation ===
The built-in Prolog predicate <code>\+/1</code> provides [[negation as failure]], which allows for [[non-monotonic logic|non-monotonic]] reasoning. The goal <code>\+ illegal(X)</code> in the rule

<syntaxhighlight lang="prolog">legal(X) :- \+ illegal(X).</syntaxhighlight>

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