Download 1. Logic Programming and Prolog: A First Glimpse

Logic Programming and Prolog
69
______________________________________________________________
(6.7) Find out what the following program does and how it works. Try to predict the
behaviour of each predicate as exactly as possible, and then experiment with your Prolog
interpreter.
% in(X,T) :- ???
in(X,t(X,_,_)) :- !.
in(X,t(Y,Left,_)) :- X @< Y, !, in(X,Left).
in(X,t(Y,_,Right)) :- X @> Y, in(X,Right).
% sh(T) :- ???
sh(T) :- var(T), !, write('_ ').
sh(t(X,Left,Right)) :write(X), write(' '), sh(Left), sh(Right).
% do(T) :- ???
do(T) :- in(2,T),in(5,T),in(7,T),in(3,T),in(7,T),sh(T).
Suppose a data structure T has been constructed with a sequence of in/2 calls. Write a
predicate that prints all nonvar elements of T in ascending order.
Summary
•
Incomplete data structures can be very useful for problems in which relations
between objects are given (or determined) in an irregular, complicated pattern.
Examples are some types of scheduling problems, where many different and
complicated boundary conditions must be met.
•
The idea of incomplete data structures lead to the powerful programming technique
of difference-lists. This techique uses lists of elements, with the last element being a
variable; i.e. a (yet) uninstantiated remainder list.
•
Difference-lists can be used to implement FIFO queues.
•
Another important application of difference-lists is string parsing.
Some Good Books
William F. Clocksin and Christopher S. Mellish, Programming in Prolog, Second Edition,
Springer-Verlg, Heidelberg, 1984, ISBN 3-540-15011-0. (Prolog Standard)
Ivan Bratko, Prolog Programming for Artificial Intelligence, Second Edition, AddisonWesley, Wokingham, England, 1993, ISBN 0-201-41606-9.
Leon Sterling and Ehud Shapiro, The Art of Prolog, Advanced Programming Techniques, The
MIT Press, Cambridge, Mass., 1986, ISBN 0-262-69105-1.