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.
Compound terms with functors that are declared as operators can be written in prefix or infix notation.
Users can declare arbitrary functors as operators with different precedences to allow for domain-specific notations.
Pure Prolog is restricted to Horn clauses, a Turing-complete subset of first-order predicate logic.
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.
In that case, all generated variable bindings are reported to the user, and the query is said to have succeeded.
Therefore, deterministic tail-recursive predicates are executed with constant stack space, like loops in other languages.
inside a rule will prevent Prolog from backtracking any predicates behind the cut: will fail if the first-found value of X for which one(X) is true leads to two(X) being false.
For instance searching a list for a given value: The built-in Prolog predicate \+/1 provides negation as failure, which allows for non-monotonic reasoning.
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.
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.
Given the sentence expressed in Backus–Naur form: This can be written in Prolog using DCGs, corresponding to a predictive parser with one token look-ahead: This code defines a relation between a sentence (given as a list of tokens) and its abstract syntax tree (AST).
Example query: 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: