Information Technology Reference
In-Depth Information
<structure> ::= <function><term> {, <term>}
<function> ::= <atom>
List is an important data structure supported by Prolog. A list can be
represented as a binary function cons(X, Y), with X the head of the list and Y the
tail. The tail Y of a list cons(X, Y) is also a list which can be generated by
deleting the element X from cons(X, Y). Elements of a list can be atoms,
structures, terms and lists. Table 2.1 shows some notations on lists that be used in
Prolog.
Table 2.1 Prolog list structure
empty table
[ ] or nil
[ a ]
cons(a,nil)
cons(a,cons(b,nil))
[ a, b ]
[ a, b, c ]
cons(a,cons(b,cons(c,nil))
[ X | Y ]
cons(X,Y)
[ a, b | c ]
cons(a,cons(b,c))
Finally we present an example on which recursion is used in programs of
Prolog. Consider a simple predicate that checks if an element is a member of a
list. It has the two clauses listed below:
member(X, [X |_ ]).
member(X,[_|Y]) :- member(X,Y).
In this example, the predicate member is recursively defined, with the first
Horn clause be the boundary condition and the second the recursive case.
2.2.3
SLD resolution
SLD resolution is the basic inference rule used in logic programming. It is also
the primary computation procedure used in PROLOG. Here the name SLD is an
abbreviation of “Linear resolution with Selection function for Definite clauses”.
Firstly we introduce definitions on definite clause.
Definition 2.3
A Definite clause is a clause of the form
