Introduction to
Logic Programming
What
versus
How
 

Chapter 10 - Lists, Sets, Trees


10.1 Introduction

In this chapter, we begin our look at view definitions involving constructors and compound terms. The examples here concern the representation of information about lists and trees and sets. In the chapters that follow, we look at the representation of information about dynamic systems and the representation of metaknowledge (i.e. information about information).

10.2 Example - Peano Arithmetic

Peano Arithmetic is that branch of Mathematics having to do with the non-negative integers, the function of addition, and the less than relation.

Peano Arithmetic is more complicated than Modular Arithmetic in that we have infinitely many objects to consider, viz. the integers 0, 1, 2, 3, ... Since there are infinitely many such numbers, we need infinitely many terms to describe them in our language.

One way to get infinitely many terms is by expanding our vocabulary to include infinitely many symbols. Unfortunately, this would make the job of defining arithmetic impossible, as we would have to write out infinitely many sentences.

Fortunately, there is a better way. In particular, we can represent numbers using a single symbol (e.g. 0) and a single unary constructor (e.g. s). In this approach, we represent the number 0 with the symbol 0, and we represent every other natural number n by applying the constructor s exactly n times. For example, in this encoding, s(0) represents 1; s(s(0)) represents 2; s(s(s(0))) represents 3; and so forth. With this encoding, we automatically get an infinite set of ground terms.

Unfortunately, even with this representation, defining Peano Arithmetic is more challenging than defining Modular Arithmetic. We cannot write all of the facts to characterize addition and multiplication and so forth, because there are infinitely many cases to consider. For Peano Arithmetic, we must rely on view definitions, not just because they are more economical but because they are the only way we can characterize these concepts in finite space.

Let's look at the number predicate first. The rules shown here define the number relation in terms of 0 and s.

number(0)
number(s(X)) :- number(X)

The next predicate holds of any natural number and the number that follows it. For example, we have next(0,s(0)) and next(s(0),s(s(0))) and so forth. We can define next in general as shown below.

next(X,s(X)) :- number(X)

Once we have number and next, we can define the usual arithmetic relations. For example, the following sentences define the add relation. Adding 0 to any number results in that number. If adding a number X to a number Y produces a number Z, then adding the successor of X to Y produces the successor of Z.

add(0,Y,Y) :- number(Y)
add(s(X),Y,s(Z)) :- add(X,Y,Z)

Using next, we can also define the less than relation in an analogous manner. A number X is less than a number Z if next holds of X and Z or if there is a number Y such that Y is the number after X and Y is less than Z.

less(X,Z) :- next(X,Z)
less(X,Z) :- next(X,Y) & less(Y,Z)

Before we leave our discussion of arithmetic, it is instructive to look at the concept of Diophantine equations. A polynomial equation is a sentence composed using only addition, multiplication, and exponentiation with fixed exponents (that is numbers not variables). For example, the expression shown below in traditional math notation is a polynomial equation.

x2 + 2y = 4z

A natural Diophantine equation is a polynomial equation in which the variables are restricted to the non-negative integers. For example, the polynomial equation here is also a Diophantine equation and happens to have a solution in the non-negative numbers, viz. x=4 and y=8 and z=8.

Diophantine equations can be readily expressed as sentences in Peano Arithmetic. For example, we can represent the Diophantine equation above with the rule shown below.

solution(X,Y,Z) :- mul(X,X,X2) & mul(s(s(0)),Y,2Y) & mul(s(s(s(s(0)))),Z,4Z) & add(X2,2Y,4Z)

This is a little messy, but it is doable. And we can always clean things up by adding a little syntactic sugar to our notation to make it look like traditional math notation.

10.3 Lists

A list is a finite sequence of objects. Lists can be flat, e.g. [a, b, f(c), d]. Lists can also be nested within other lists, e.g. [a, [b, f(c)], d].

To talk about lists of arbitrary length, we use the binary constructor cons, and we use the symbol nil to refer to the empty list. In particular, a term of the form cons1, τ2) designates a list in which τ1 denotes the first element and τ2 denotes the rest of the list.

For example, using this approach, we can represent the list [a, b, c] with the compound term shown below.

cons(a, cons(b, cons(c, nil)))

Rules defining primitives and lists.

primitive(a)
primitive(b)
primitive(c)

list(nil)
list(cons(X,Y)) :- object(X) & list(Y)

object(X) :- primitive(X)
object(X) :- list(X)

The advantage of this representation is that it allows us to describe relations on lists without regard to length or depth.

As an example, consider the definition of the binary relation mem, which holds of an object and a list if the object is a top-level mem of the list. Using the constructor cons, we can characterize the mem relation as shown below. Obviously, an object is a mem of a list if it is the first element; however, it is also a mem if it is mem of the rest of the list.

mem(X,cons(X,Y)) :- object(X) & list(Y)
mem(X,cons(Y,Z)) :- object(Y) & mem(X,Z)

In similar fashion, we can define other relations on lists. For example, the following rules define a relation called app. The value of app (its last argument) is a list consisting of the elements in the list supplied as its first argument followed by the elements in the list supplied as its second. For example, we would have app(cons(a,nil), cons(b, cons(c, nil)), cons(a, cons(b, cons(c, nil)))).

app(nil,Y,Y) :- list(Y)
app(cons(X,Y),Z,cons(X,W)) :- object(X) & app(Y,Z,W)

Finally, a note on syntax. There are three ways to write lists - using square brackets, using cons, and using the ! operator.

If we know all of the elements of a list, we can write the list by wrapping the elements in square brackets and separating them with commas, as in the example shown below.

[a,b,c]

This list can also be represented using the cons constructor, as shown below.

cons(a, cons(b, cons(c, nil)))

In order to abbreviate the representation of lists, we can alternatively use the ! operator in place of cons. For example, we would write the list just discussed as shown below.

a!b!c!nil

All three of these representations are equivalent. In fact, they typically parse into the same internal representation. However, they each have value in different circumstances, and so all three are permitted.

Lists are an extremely versatile representational device, and the reader is encouraged to become as familiar as possible with the techniques of writing definitions for relations on lists. As is true of many tasks, practice is the best approach to gaining skill.

10.4 Example - Sorted Lists

A sorted list is a list in which successive elements satisfy a given ordering relation. For example, the list [1,2,3] is a sorted list with "less than" as the ordering relation, while [1,3,2] is not.

Note that it is common for objects to appear more than once in a sorted list. For example, [1,2,2,3] is a sorted list with "less than or equal" as the ordering relation. However, this cannot happen if the ordering relation is not reflexive. For example, [1,2,2,3] is not a sorted list with "less than" as the ordering relation.

Given an ordering relation (e.g. the "less than or equal" relation leq), we can easily define a predicate sorted that is true of sorted lists and false of everything else. See below. The empty list is sorted. Any list of one element is sorted. A list of two or more elements is sorted if the first element is less than or equal to the second and the tail of the list is sorted.

sorted(nil)
sorted([X]) :- object(X)
sorted(cons(X,cons(Y,L))) :- leq(X,Y) & sorted(cons(Y,L))

As with unsorted lists, we can define relations on sorted lists as well. However, in doing so we must ensure that the resulting lists are sorted. Although the app relation defined earlier can be applied to sorted lists, the result may not be sorted.

One way to deal with this is to apply a sorter to a list to ensure that it is sorted. For example, the following view definition defines a sorting relation sortappend in terms of app and sort.

sortappend(X,Y,Z) :- app(X,Y,W) & sort(W,Z)

This approach works, and it yields the correct answer (even when the input lists are not sorted). However, if we know that the input lists are sorted, it is possible to define a sorting relation in another way.

merge(nil,Y,Y) :- list(Y)
merge(X!L,Y,Z) :- merge(L,Y,W) & insert(X,W,Z)

For many people, this version is more appropriate than the version above. Moreover, as we shall see when we get to program execution, it may execute more efficiently than the preceding version.

10.5 Example - Sets

A set is a collection of objects. A set differs from a list in two ways. (1) Objects can appear in lists more than once whereas this cannot happen in a set. (2) The order of elements in a list is essential whereas order is irrelevant for sets.

In what follows, we represent sets as ordered lists. Since order is irrelevant in a set, it does not matter which order we choose, and keeping things ordered makes it easier to define certain relations on sets; and, as we shall see in later lessons, it makes query answering more efficient.

If we represent sets as lists, we can see whether an object is a member of the set using the mem relation defined earlier. However, if we represent sets as ordered lists, there is a better way. See below.

mem(X,X!L) :- list(L)
mem(X,Y!L) :- less(Y,X) & mem(X,L)

As with the definition of list membership, this version loops through the elements of the set. Also, if we get to a subset with the object as the first element, then we terminate successfully. The main difference here is that we can sometimes stop early if an object is not an element of the set. In particular, if, in looping through sublists of the sublist, we get to a sublist in which the specified object is less than the first element, then we can stop searching since we know that all subsequent objects in the list are greater than that element.

One set is a subset of another if and only if every element of the first set is an element of the second. We can define the subset relation as shown below.

subset(nil,Y) :- list(Y)
subset(X!L,Y) :- mem(X,Y) & subset(L,Y)

The intersection two sets is the set consisting of all objects that appear in both sets.

intersection(nil,Y,nil) :- list(Y)
intersection(X!L,Y,X!Z) :- mem(X,Y) & intersection(L,Y,Z)
intersection(X!L,Y,Z) :- ~mem(X,Y) & intersection(L,Y,Z)

The union of two sets is the set consisting of all elements in either set. If we represent sets as sorted lists, then union is identical to the merge relation defined earlier.

10.6 Example - Trees

The cons relation can also be used to represent arbitrary trees. For example, cons(cons(a,b),cons(c,d)) represents a binary tree with a, b, c, and d as leaves.

The among relation is true of an object and a tree if the object is appears somewhere in the tree.

among(X,X) :- object(X)
among(X,cons(Y,Z)) :- among(X,Y)
among(X,cons(Y,Z)) :- among(X,Z)

Note that, if the specified object is itself a tree, this relation is the same as the subtree relation on trees.

Exercises

Exercise 10.1: Say whether each of the following sentences is in the extension of the app relation defined in Section 10.3

a. app(nil,nil,nil)
b. app(cons(a,nil),nil,cons(a,nil))
c. app(cons(a,nil),cons(b,nil),cons(a,b))
d. app(cons(cons(a,nil),nil),cons(b,nil),cons(a,cons(b,nil)))

Exercise 10.2: last is a binary relation that holds of an object and a list if and only if the specified object is the last element of the specified list. For example, last(c,[a,b,c]) is true. Write a logic program that defines the last relation.

Exercise 10.3: rev is a binary relation on lists. The relation holds of two lists if and only if the second contains the same elements as the first except in the opposite order. For example, rev([a,b,c],[c,b,a]) is true. Write a logic program that defines the rev relation. Hint: It helps to define a variation on app and then use that variation in defining rev.

Exercise 10.4: delete is a ternary relation that holds of an object and two lists if and only if the second list is a copy of the first list with all occurrences of the given object deleted. For example, delete(b,[a,b,c,b,d],[a,c,d]) is true. Write a logic program that defines the delete relation.

Exercise 10.5: substitute is a 4-ary relation that holds of two objects and two lists if and only if the second list is a copy of the first list with all occurrences of the second object replaced by the first object. For example, substitute(b,d,[a,d,d,c],[a,b,b,c]) is true. Write a logic program that defines the substitute relation.

Exercise 10.6: adjacent is a ternary relation that holds of two objects and a list if and only if the first object and the second object are adjacent to each other in the specified list. For example, adjacent(b,c,[a,b,c,d]) is true. Write a logic program that defines the adjacent relation.

Exercise 10.7: sublist is a binary relation that holds of two lists if and only if the first list is a contiguous sublist of the second. For example, sublist([b,c],[a,b,c,d]) is true while sublist([b,d],[a,b,c,d]) is not. Write a logic program that defines the sublist relation.

Exercise 10.8: sort is a binary relation that holds of two lists if and only if the second list is a version of the first in sorted order. For example, sort([2,1,3,2],[1,2,2,3]) is true. Write a logic program that defines the sort relation in terms of min.

Exercise 10.9: powerset is a binary relation that holds of two sets if and only if the second set is the powerset of the first set, i.e. the second is the set of all subsets of the first set. For example, powerset([a,b],[[],[a],[b],[a,b]]) is true. Write a logic program that defines the powerset relation.