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 ?-
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.
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 ?-