User:Robert Kowalski/sandbox

definition __________________________________________________________________________

The text below was originally intended for the Computer program entry. I edited the entry with a much shorter text.

The remainder can be used elsewhere. But where?

____________________________________________________________________

In the simplest case of Horn clauses (or "definite" clauses), all of the H, B₁, ..., B_n are atomic formulae of the form p (t₁ ,…, t_n), where p is a predicate symbol naming a relation, and the t_n are terms naming objects (or individuals). Terms can be constants, variables or composite terms of the form f (t₁ ,…, t_n), where f is a functor (or function symbol) and the t_n are terms. Variables are written as a string beginning with an upper case letter or an underscore.

For example:

• All dragons smoke, or equivalently, a thing smokes if the thing is a dragon:

smokes(X) :-
    is_a_dragon(X).

• A creature smokes if one of its parents smokes:

smokes(X) :-
    is_a_creature(X),
    is_a_parent_of(Y,X),
    smokes(Y).

• A thing X is a parent of a thing Y if X is the mother of Y or X is the father of Y:

 
is_a_parent_of(X, Y):- is_the_mother_of(X, Y).
is_a_parent_of(X, Y):- is_the_father_of(X, Y).

• A thing is a creature if the thing is a dragon:

is_a_creature(X) :-
    is_a_dragon(X).

• Alice is a dragon, and Bob is a creature. Alice is the mother of Bob.

is_a_dragon(alice). 
is_a_creature(bob).
is_the_mother_of(alice, bob).

The example illustrates several features of Prolog and of logic programs more generally: All of the variables in a clause are universally quantified, meaning that the clause holds for all instances in which the variables are replaced by terms not containing variables. Also, all variables are local to the clause in which they occur. So, there is no relationship, for example, between the variables X and Y in the second clause and the variables X and Y in the third clause. (In fact, their roles in the parent relation in the two clauses are actually reversed.)

Notice that the second clause is a recursive (or inductive) definition. It can be understood purely declaratively, without any need to understand how it is executed. The third clause shows how functions, as in functional programming, are represented by relations. Here the mother and father relations are functions in the sense that every individual has only one mother and only one father.

Prolog is an untyped language. However, types (or classes) can be represented by predicates. The fourth clause defines dragon as a subtype (or subclass) of creature.

Computation in Prolog can be regarded as question-answering or theorem-proving. It is initiated by a query or theorem to be proved, and solutions are generated by backward reasoning. For example:

• Answer the query: which thing smokes? Or, equivalently, prove that some thing smokes!

 ?- smokes(X).

All variables in queries are existentially quantified, and execution of the program generates instances of the query that make the query true.

In the case where all clauses are Horn clauses, backward reasoning is performed by using SLD resolution, which is a variant of SL resolution for Horn clauses (or definite clauses). In this example, backward reasoning uses the first clause to reduce the goal to the subgoal:

 ?- is_a_dragon(X).

and it uses the second clause to reduce the goal to the subgoals:

 ?-  is_a_creature(X),
    is_a_parent_of(Y,X),
    smokes(Y).

It solves the subgoal is_a_dragon(X) generated by the first clause, by unifying it with the fact is_a_dragon(alice), instantiating the variable X to the constant alice, giving the solution, X = alice. It solves the three subgoals generated by the second clause, by unifying them with the facts is_a_creature(bob), is_a_parent_of(alice, bob) and smokes(alice), instantiating the variable X to the constant bob, giving a second solution, X = bob.

Goal-reduction, performed in this way, generates a generalised form of and-or tree of goals and subgoals. Prolog explores this tree depth-first, trying different clauses unifying with the same subgoal in the order in which the clauses are written, and trying to solve different subgoals coming from the same clause in the order in which the subgoals are written in the clause. In this example, the computation will generate the solution, X = alice, followed by X = bob.

Prolog programs can also include negative conditions in the body of clauses, as in:

• A creature is healthy if the creature does not smoke:

is_healthy(X) :-
    is_a_creature(X),
    not smokes(X).

Prolog uses negation as failure (NAF) to solve negative subgoals of the form not pby showing that the corresponding unnegated subgoal p fails to hold. For example, the query:

 ?- not healthy(bob).

returns the answer true, because the query

 ?- healthy(bob).

fails, because the subgoal:

 ?- not smokes(bob).

fails, because:

 ?- smokes(bob).

succeeds.

Prolog is a homoiconic language, in which atomic formulae and clauses are represented by composite terms. This is a powerful feature which has many applications, including its use for implementing metainterpreters and for representing and reasoning about propositional attitudes. For example:

• It is prohibited for a creature that the creature teaches deportment if the creature smokes. A creature is ostracised if it is prohibited for the creature that a thing and the thing holds:

prohibited(X, teaches(X, deportment)) :- creature(X), smokes(X).
ostracised(X) :- creature(X), prohibited(X, P), holds(P).

The simplest case in which a proposition P holds is defined by:

holds(A) :- clause(A, true).

where

clause(Head, Body)

is a built-in metapredicate that holds when Head can be unified with the head of a clause and Body can be unified with the corresponding clause body, where Body = true if the clause is a fact.

Given the fact (assumption or premise):

teaches(bob, deportment).

and the query:

ostracised(X).

Prolog derives the answer X = bob

These examples illustrate some of the unique features of Prolog, which distinguish it from more conventional programming languages, and which highlight its use as a logic-based language for knowledge representation and problem solving in Artificial Intelligence.

Prolog has many applications. But many large-scale applications require the use of Prolog's "impure features", which do not have an obvious logical interpretation, or they are implemented in combination with other programming languages. The broad range of Prolog applications, both in isolation and in combination with other languages is highlighted in the Year of Prolog Book , celebrating the 50 year anniversary of Prolog.