Concepts of Programming Languages

756 Chapter 16 Logic Programming Languages

which would succeed, because its argument had failed. Finally, the result, which

is X, would be printed. But X would not be currently instantiated, so the system

would indicate that. Generally, uninstantiated variables are printed in the form

of a string of digits preceded by an underscore. So, the fact that Prolog’s not is

not equivalent to a logical NOT can be, at the very least, misleading.

The fundamental reason why logical NOT cannot be an integral part of

Prolog is the form of the Horn clause:

A :- B 1 x B 2 x... x Bn

If all the B propositions are true, it can be concluded that A is true. But regard-

less of the truth or falseness of any or all of the B’s, it cannot be concluded that

A is false. From positive logic, one can conclude only positive logic. Thus, the

use of Horn clause form prevents any negative conclusions.

16.7.4 Intrinsic Limitations

A fundamental goal of logic programming, as stated in Section 16.4, is to pro-

vide nonprocedural programming; that is, a system by which programmers

specify what a program is supposed to do but need not specify how that is to be

accomplished. The example given there for sorting is rewritten here:

sort(old_list, new_list) permute(old_list, new_list) x sorted(new_list)

sorted(list) 5 j such that 1...j 6 n, list( j)...list( j+1)

It is straightforward to write this in Prolog. For example, the sorted subgoal

can be expressed as

sorted ([]).

sorted ([x]).

sorted ([x, y | list]) :- x <= y, sorted ([y | list]).

The problem with this sort process is that it has no idea of how to sort, other

than simply to enumerate all permutations of the given list until it happens to

create the one that has the list in sorted order—a very slow process, indeed.

So far, no one has discovered a process by which the description of a sorted

list can be transformed into some efficient algorithm for sorting. Resolution is

capable of many interesting things, but certainly not this. Therefore, a Prolog

program that sorts a list must specify the details of how that sorting can be

done, as is the case in an imperative or functional language.

Do all of these problems mean that logic programming should be aban-

doned? Absolutely not! As it is, it is capable of dealing with many useful appli-

cations. Furthermore, it is based on an intriguing concept and is therefore

interesting in and of itself. Finally, there is the possibility that new inferencing

techniques will be developed that will allow a logic programming language

system to efficiently deal with progressively larger classes of problems.