Information Technology Reference
In-Depth Information
Want to read more?
This chapter considered programming in Prolog, concentrating on programs that deal
with lists. This type of list processing, which involves dealing with collections of
symbols as single larger units, has a long history. The first truly symbolic (that is, non-
numerical) programming language, called IPL, was also the first to provide explicit
facilities for dealing with lists. A more influential and still quite popular program-
ming language of this sort is LISP [38] and its direct descendant, Scheme [53]. Both
LISP and Scheme take list processing as their central focus.
A few simple examples of list-processing predicates were reviewed in this chapter.
The blocks-world program was rewritten using lists, and many other programs in
previous chapters could be redone more clearly using lists. It takes time and practice
to master this type of programming, however. A typical second-year or third-year
undergraduate computer science course might involve writing predicates that are
similar to
append
but perhaps more complex (for example, a predicate that returns
every second element of a list, or a predicate that sorts a list of numbers into ascending
order). Any programming textbook on Prolog (such as those mentioned at the end of
chapter 4) will cover writing predicates like these.
It turns out, however, there are even more advanced list-processing techniques that
can be employed in Prolog but that do not fit well in other programming languages.
In particular, the fact that an uninstantiated variable can be an element of a list allows
certain operations to be performed very elegantly in Prolog, by building a list but
leaving parts of it unspecified at first. These techniques and many more are covered
in the more advanced Prolog textbooks such as [39].
Exercises
The text defined a predicate
elem
(
)
1.
x
,
y
that held when
x
was an element of the
list
y
. Consider the following variant:
elem3(X,[X]).
elem3(X,[_|L]) :- elem3(X,L).
Give an example of an
x
and a
y
such that
elem
(
x
,
y
)
holds but where
elem3
(
x
,
y
)
does not hold.
Describe in English when the predicate
elem3
(
x
,
y
)
holds in
general.
