CSE 360: Lecture 6

An example of tracing

In Lecture 5 we presented the following quick sort program. 
qsort nil nil.
qsort (First::Rest) Sorted :-
  split First Rest Small Big,
  qsort Small SmallSorted,
  qsort Big BigSorted,
  append SmallSorted (First::BigSorted) Sorted.
In order to trace this program, we can can add the following as its first line: 
qsort L K :- write (qsort L K), nl, fail.
This will cause the qsort goal to be printed out every time it is called. After printing the goal, a newline is printed, and a failure occurs. This fail is important since we do not want tracing to provide the program will any additional successful computations.

The following is an example of how this kind of tracing will appear on the screen. 

?- qsort (4::2::8::5::7::12::1::nil) H.
qsort (4 :: 2 :: 8 :: 5 :: 7 :: 12 :: 1 :: nil) H
qsort (2 :: 1 :: nil) K
qsort (1 :: nil) K1
qsort nil K2
qsort nil K3
qsort nil K4
qsort (8 :: 5 :: 7 :: 12 :: nil) K5
qsort (5 :: 7 :: nil) K6
qsort nil K7
qsort (7 :: nil) K8
qsort nil K9
qsort nil K10
qsort (12 :: nil) K11
qsort nil K12
qsort nil K13

H = 1 :: 2 :: 4 :: 5 :: 7 :: 8 :: 12 :: nil.

yes
?-
If you only wish to monitor the behavior of a predicate on certain kinds of values, then you can add a different kind of first line. For example, if you don't care to see the qsort goal when the first argument is nil, then you change this first line to be 
qsort (X::L) K :- write (qsort (X::L) K), nl, fail.
Then only non-empty first arguments will trigger prints of goals. 
?- qsort (4::2::8::5::7::12::1::nil) H.
qsort (4 :: 2 :: 8 :: 5 :: 7 :: 12 :: 1 :: nil) H
qsort (2 :: 1 :: nil) K
qsort (1 :: nil) K1
qsort (8 :: 5 :: 7 :: 12 :: nil) K2
qsort (5 :: 7 :: nil) K3
qsort (7 :: nil) K4
qsort (12 :: nil) K5

H = 1 :: 2 :: 4 :: 5 :: 7 :: 8 :: 12 :: nil.

yes
?-

Some uses of cut to control search

Below is code that is similar to append except that if a member of the list is already present in the list to which you are appending, that element is not also added. This can be used to control the kinds duplicates of members in a list. 
type join            list A -> list A -> list A -> o.

join nil K K.
join (X::L) K M      :- memb X K, !, join L K M.
join (X::L) K (X::M) :- join L K M.
If the cut is removed in the second clause, the program has more solutions, and duplicates would start appearring in the third argument.

Negation-by-failure

It is sometimes important in a program to be able to specify that sometime cannot be proved. Usually, lambda Prolog attempts to prove things. Using cut !, however, it is a simple matter to write a negation operator. 
type not    o -> o.

not G :- G, !, fail.
not G.
Because of the presence of cut, many uses of not do not appear to have anything to do with logical deduction. Consider, for example, the following queries. 
?- memb N (3::5::nil).

N = 3.
;

N = 5.
;
no more solutions
?- not (memb N (3::5::nil)).
no
?- not (memb 4 (3::5::nil)).
solved

yes
?- not (sigma N\(memb N (3::5::nil))).
no
?-
Lecture Directory / Module Directory / CSE360 Syllabus