Introduction to Prolog, part 3

In this note we look at structured data objects in general, and lists in particular. We first describe the general structure of data objects, and then explain how lists fit into the paradigm, despite having a special syntax which makes them look different. This program contains some commonly-defined predicates involving lists.

Structured data objects

So far all data items (such as bob, kev and so on) have been "atoms". Prolog programs can also manipulate numerical quantities, but its main strength is symbol manipulation, and that is what we are going to look at here. For example we will see how to define and manipulate propositional-logic boolean formulae made up of symbols representing "and", "or", "not" and boolean variables.

The structured data objects that prolog deals with (such as boolean formulae) have a tree-like structure. Within a (parsed) boolean formula, every "and" and "or" would connect two subformulae, and every "not" would apply to one subformula. Prolog manipulates terms, built up from atoms (such as variable symbols) and functors which are the connectives that glue together subterms. A functor is a symbol that takes some fixed number of terms, each of which is a subtree attached below a node labelled by that functor's label. A term is represented syntactically by its top-level functor, followed by the subterms, in a sequence separated by commas and enclosed in parentheses.

By way of example, consider the code shown below. It is designed to manipulate expressions built up from functors a and o (representing boolean "and" and "or", hence having two arguments), also functor n (representing "not", having one argument), and atoms which represent propositional variables.

The first program defines a predicate cnf which is satisfied by boolean formulae which are in conjunctive normal form, in the sense that any conjunction operators will always be above everything else, followed by disjunction operators, followed by monomials.

monomial(X) :- atom(X).        % any atom is treated as a boolean variable,
monomial(n(X)) :- atom(X).     % so an atom or its negation is a monomial
                               % (Note: atom is a built-in predicate)

disjunction(X) :- monomial(X).   % any monomial is a disjunction

disjunction(o(X,Y)) :- disjunction(X), % in addition, a disjunction may be
                       disjunction(Y). % the binary functor "o" with subtrees
                                       % both of which are disjunctions.

cnf(X) :- disjunction(X).        % any disjunction is a (one-clause) cnf.

cnf(a(X,Y)) :- disjunction(X),   % predicate cnf is satisfied by any term
               disjunction(Y).   % which is an "a" whose subtrees are
                                 % disjunctions

cnf(a(X,Y)) :- cnf(X), cnf(Y).   % or alternatively any term consisting of
                                 % an "a" whose subtrees are cnfs

Let us go through it in a bit more detail. The first lines are:

monomial(X) :- atom(X).
monomial(n(X)) :- atom(X).

the first of which uses the built-in predicate "atom" which is satisfied by atoms, such as bob, ted, etc. We regard any atom as representing a boolean variable. Recall that a monomial is a boolean variable or its negation, and we are using the notation n(var) for the negation of variable var. n(var) is not an atom; it consists of the functor n whose one argument is the atom var.

Moving down, the predicate "disjunction" is defined as follows.

disjunction(X) :- monomial(X).

disjunction(o(X,Y)) :- disjunction(X),
                       disjunction(Y).

X is a disjunction if it is a monomial, or alternatively X is a disjunction if it consists of the functor o whose two subterms are themselves disjunction. Between them, these two clauses define disjunction to be terms whose tree diagrams have internal nodes of degree 2 labelled by o, leaves with any labels, and some internal nodes of degree 1 labelled by n which may occur immediately above leaves. These structures are all interpreted by the subsequent predicates as being boolean formulae where o means "or" and n means "not".

For example the program answers queries such as the following ones:

| ?- cnf( o(a(x1,n(x2)), a(n(x1),x3))).

no
| ?- cnf( a(o(x1,n(x2)), a(n(x1),x3))).

yes
| ?-

In the first case there is an "or" above an "and", so the answer is no. In the second case (where the first or and and have been switched), the answer is yes.

The second program defines a predicate givecnfequiv which takes a boolean formula as input, and prints a logically equivalent expression in conjunction normal form. For the purposes of this program, conjunctive normal form (as defined by the predicate cnf above) means that an expression consists of a tree with all a's above all all o's, all o's above all n's, and with propositional variables at the bottom. So we can make a query such as the following:

| ?- givecnfequiv( o(a(x1,n(x2)), a(n(x1),x3))).
a(a(o(x1,n(x1)),o(n(x2),n(x1))),a(o(x1,x3),o(n(x2),x3)))
yes
| ?-

The formula in the query has the tree structure:

          __o__
         /     \
        a       a
       / \     / \
      x1  n   n   x3
          |   |
          x2  x1

The answer was a boolean formula with the following structure, and which is logically equivalent under the interpretation that a means "and, o means "or", n means "not, and everything else is a variable. The formula is in conjunctive normal form, in the sense that it is a conjunction of disjunctions. (Note that it is not as simple as possible, in particular the first disjunctive clause is tautologous.)

          ____a_____
         /          \
       _a__          a_
      /    \        /  \
     o      o      o    o
    / \    / \    / \  / \
   x1  n  n   n  x1 x3 n  x3
       |  |   |        |
       x1 x2  x1       x2

The program is as follows:


 % givecnfequiv prints out a CNF equivalent formula of its argument

givecnfequiv(X) :- cnfequiv(X,Y), write(Y). % write is a built-in predicate
                                            % which prints its argument

 % cnfequiv is designed for queries in which the first argument is a
 % boolean formula and the second is a variable - the variable will be
 % instantiated to an equivalent formula of the first argument, in
 % conjunctive normal form (meaning it would satisfy the "cnf" predicate
 % in the program "cnfs.prolog"). Given a query of this form, the first
 % clause in the definition is repeatedly invoked until the subgoal
 % "transform(X,Z)" can no longer be satisfied. (See below for notes
 % on transform)

cnfequiv(X,Y) :- transform(X,Z), cnfequiv(Z,Y).
cnfequiv(X,X).

 % transform is satisfied if its second argument is derived from its
 % first by applying one of the standard transformations. Given a query
 % in whic the first argument is a boolean formula and the second is a
 % variable, it will instantiate the variable to a logically equivalent
 % formula to the first argument, which is nearer to being in conjunctive
 % normal form. If the first argument is already in conjunctive normal form
 % then the goal cannot be satisfied.

transform(n(n(X)),X).  % eliminate double negation

transform(n(a(X,Y)),o(n(X),n(Y))).  % De Morgan
transform(n(o(X,Y)),a(n(X),n(Y))).  %

transform(o(X,a(Y,Z)),a(o(X,Y),o(X,Z))).   % distribution
transform(o(a(X,Y),Z),a(o(X,Z),o(Y,Z))).   %

transform(o(X1,Y),o(X2,Y)) :- transform(X1,X2).  %
transform(o(X,Y1),o(X,Y2)) :- transform(Y1,Y2).  %
                                                 % transform subterms
transform(a(X1,Y),a(X2,Y)) :- transform(X1,X2).  %
transform(a(X,Y1),a(X,Y2)) :- transform(Y1,Y2).  %
                                                 %
transform(n(X1),n(X2)) :- transform(X1,X2).      %

The above code is partly derived from an example in Bratko's textbook, but adapted so as not to use advanced features of Prolog.

Lists

A list is a compound data object made up of a sequence of separate data objects (the entries in the list). In prolog, a list has an underlying tree structure (fitting in with the paradigm of compound data objects being constructed using functors), but lists have a special syntax which hides this structure and looks more like typical list notation.

The list of atoms a, b and c would be denoted [a,b,c]. There is an underlying structure to this notation, namely the atoms are glued together by the binary functor . (the full stop) whose first argument is the head of a list and whose second argument is the sublist caused by removing the head. The empty list is the atom []. Hence [a,b,c] has the structure

and could equivalently be written as .(a,.(b,.(c,[]))). But this is not so readable!

Another useful piece of syntax is the vertical bar "|" within a list. In particular, [Head|Tail] denotes the list you get by appending data object Head to the list Tail. We can use this convenient notation to define predicates like "within" (having two arguments) to be satisfied if its second argument is a list of which its first argument is a member.

within(Head,[Head|Tail]).
within(X,[Head|Tail]) :- within(X,Tail).

Concatenating and reversing lists

% concat(A,B,C) means if you concatenate A with B you get C
concat([],List,List).
concat([A|L1],L2,[A|L3]) :- concat(L1,L2,L3).

% reverse(A,B) means that A is the reverse if B
% works for queries of the form reverse([given list],A); for queries
% of the form reverse(A,[list]) loops for ever after you reject the 
% answer
reverse([],[]).
reverse([A|L1],L2) :- reverse(L1,L3), concat(L3,[A],L2).

Department main page

Paul Goldberg's home page