Programmer 7500

home *** CD-ROM | disk | FTP | other *** search

/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / TP_ALGO.ZIP / TP_ALGO.TXT

Wrap

Text File | 1986-05-27 | 31.6 KB | 724 lines

Expressing Procedural Algorithms in Prolog Michael A. Covington Research Report 01-0012 Advanced Computational Methods Center University of Georgia Athens, Georgia 30602 May 26, 1986 4:25 pm -------------------------------------------------------------- This work was supported by PACER Grant 85PCR18 from Control Data Corporation and by Grant Number INS-85-02477 from the National Science Foundation. The opinions expressed here are solely those of the author. The assistance of Donald Nute and Andre Vellino is gratefully acknowledged. Printed copies of this and other research reports are available free on request. -------------------------------------------------------------- With the increasing popularity of Prolog as an application programming language, it is often necessary to develop Prolog equivalents for algorithms that were originally expressed in procedure-oriented languages. This paper presents a number of strategies for doing so. I assume that the reader is already familiar with the basic mechanisms of Prolog -- unification (matching), backtracking, and the like. Unless otherwise noted, the examples given here work both in full "Edinburgh" or "DEC-10" Prolog (Clocksin and Mellish 1984) and in Turbo Prolog (1986), which is a subset of the full language. The examples are written in Turbo Prolog syntax, but with declarations omitted for brevity. Full Prolog is used -- and noted as such -- when its features are needed. The procedural interpretation of logic Prolog is often described as a non-procedural language. In reality, it is a semi-procedural language -- a compromise between procedural and non-procedural programming, giving some of the advantages of each. In a truly non-procedural language, the programmer would provide only a logically rigorous set of conditions that the program must fulfill; the computer would then automatically generate an algorithm from them. Such things as the order in which the conditions were written would have no effect. In the interest of efficiency, Prolog contains some procedural elements. The Prolog programmer specifies not only the rules of inference to be used in solving a problem, but also the order in which they are to be tried. Crucially, the programmer can even specify that some potential paths to a solution should not be tried at all. This makes it possible to perform efficiently many 2 computations that would be severely inefficient, or even impossible, in pure Prolog. The key principle of Prolog is the procedural interpretation of logic. Consider the following Prolog rule set: [1] in_north_america(X) :- in_usa(X). in_usa(X) :- in_georgia(X). in_georgia(atlanta). This can be interpreted as a set of facts ([2] below) or as a set of procedure definitions ([3] below). [2] X is in North America if X is in the USA. X is in the USA if X is in Georgia. Atlanta is in Georgia. [3] To prove that X is in North America, prove that X is in the USA. To prove that X is in the USA, prove that X is in Georgia. To prove that Atlanta is in Georgia, do nothing. The unfamiliar task of drawing inferences from data is thereby reduced to the very familiar task of calling procedures. In what follows I will unashamedly refer to Prolog predicate definitions as procedures. Conditional execution One of the most important differences between Prolog and other programming languages is that, in general, Prolog procedures have multiple definitions (clauses), each applying under different conditions. In Prolog, conditional execution is expressed, not with if or case statements, but with these alternative definitions of procedures. Consider for example how we might translate into Prolog the following Pascal procedure: [4] procedure writename(X:integer); begin case X of 1: write('One'); 2: write('Two'); 3: write('Three') end end; This is done by giving writename three definitions: 3 [5] writename(1) :- write("One"). writename(2) :- write("Two"). writename(3) :- write("Three"). Each definition matches in exactly one of the three cases. A common mistake is to write the clauses as follows: [6] /* bad style */ writename(X) :- X=1, write("One"). writename(X) :- X=2, write("Two"). writename(X) :- X=3, write("Three"). This gives correct results but is needlessly inefficient. It is a waste of time to go into an inapplicable clause, perform a test that fails, backtrack out, and try another clause, when the use of the inapplicable clause could have been avoided in the first place. A key to effective programming in Prolog is making each logical unit of the program into a separate procedure. Each if or case statement should, in general, become a procedure call. For example, the hypothetical Pascal procedure: [7] procedure a(X:integer); begin b; if X=0 then c else d; e end; should go into Prolog as follows: [8] a(X) :- b, c_or_d(X), e. c_or_d(0) :- c. c_or_d(X) :- X<>0, d. This imposes a disciplined organization on the program that is even more rigorous than the structured ("go-to-less") programming that serves as the basis of Pascal, Ada, and C. Guarded command sets As Kluzniak and Szpakowicz (1985) have pointed out, Dijkstra's "guard" concept (Dijkstra 1975) is easily expressed in Prolog. A guarded command set is a structure of the form 4 [9] if C1 -> A1 C2 -> A2 C3 -> A3 fi where C1, C2, and C3 are conditions and A1, A2, and A3 are the corresponding actions. During program execution, all the conditions are evaluated. If all of the conditions are false, the program terminates. Otherwise, one of the actions corresponding to a true condition is selected for execution. If exactly one condition is true, the guarded command set is equivalent to an if-then or case statement. In fact, the Prolog procedure "c_or_d" in [8] can be expressed in more Dijkstra-like (though less efficient) form as: [10] c_or_d(X) :- /* condition */ X=0, /* action */ c. c_or_d(X) :- /* condition */ X<>0, /* action */ d. Guarded command sets were developed as part of a system for deriving algorithms from formal specifications of the problems they must solve. In Dijkstra's system, if more than one condition is true, no assumptions are made about which action will be taken. In Prolog, all possible actions will be taken on successive backtracking passes, in the order in which they are given in the program. The "cut" operator Let's consider another version of "writename" ([4] above) that includes a "catch-all" clause to deal with numbers whose names are not given. In many extended forms of Pascal, this can be expressed as: [11] procedure writename(X:integer); begin case X of 1: write('One'); 2: write('Two'); 3: write('Three') else write('Out of range') end end; One way to express this in Prolog is the following: 5 [12] writename(1) :- write("One"). writename(2) :- write("Two"). writename(3) :- write("Three"). writename(X) :- X<1, write("Out of range"). writename(X) :- X>3, write("Out of range"). This gives correct results but lacks conciseness. In order to make sure that only one clause is applicable to each number, we have had to add two more clauses. What we would like to say is that the program should print "Out of range" for any number that has not matched any of the first three clauses. We could try to express this as follows, with some lack of success: [13] /* incorrect */ writename(1) :- write("One"). writename(2) :- write("Two"). writename(3) :- write("Three"). writename(_) :- write("Out of range"). (Recall that the anonymous variable, written _, matches anything.) The problem here is that the goal "writename(1)", for example, matches both the first clause and the last clause. If a subsequent goal fails and causes backtracking through this one, the goal "writename(1)" will have two solutions, one that prints "One" and one that prints "Out of range." We want "writename" to be deterministic, that is, to give exactly one solution for any given set of parameters, and not give alternative solutions upon backtracking. We would therefore like to specify somehow that if any of the first three clauses succeeds, the computer should not try the last clause. This can be done with the "cut" operator (written as an exclamation mark). The cut operator commits the computer to take a particular solution (or potential solution) without trying alternatives. Suppose for example that we have the following rule set: [14] b :- c, d, !, e, f. b :- g, h. and that the current goal is "b". If we take the first clause and execute the cut, then it becomes impossible to look for alternative solutions to "c" and "d" (the goals that precede the cut in the same clause) or to "b" (the goal that invoked the clause containing the cut). It remains possible, of course, to backtrack all the way past "b" and look for alternatives to the clause that caused "b" to be invoked. What we need to do in [13] is to put a cut in each of the first three clauses. This changes their meaning slightly, so that the first clause (for example) says, "If the parameter is 1, then write 'One' and do not try any other clauses." 6 [15] writename(1) :- !, write("One"). writename(2) :- !, write("Two"). writename(3) :- !, write("Three"). writename(_) :- write("Out of range"). Since "write" is deterministic, it does not matter whether the cut is written before or after the call to "write". However, programs are usually more readable if cuts are made as early as possible. Making procedure calls always succeed or always fail In order to control the flow of program execution, it is often necessary to guarantee that a goal will always succeed regardless of the results of the computation that it performs. Occasionally, it is necessary to guarantee that a goal will always fail. An easy way to make any procedure succeed is to add an additional clause to it that succeeds with any parameters, and is tried last, thus: [16] f(X,Y) :- X < Y, !, write("X less than Y"). f(_,_). A call to "f" succeeds with any parameters; it may or may not print its message, but it will certainly not return failure and hence will not cause backtracking in the procedure that invoked it. Moreover, because of the cut, "f" is deterministic. The cut prevents the second clause from being used to generate a second solution with parameters that have already succeeded with the first clause. Similarly, a procedure can be guaranteed to fail by adding cut and fail at the end of each of its definitions, thus: [17] g(X,Y) :- X<Y, write("X less than Y"), !, fail. g(X,Y) :- Y<X, write("Y less than X"), !, fail. Any call to "g" ultimately returns failure for either of two reasons: either it doesn't match any of the clauses, or it matches one of the clauses and ends with cut and fail. The cut is written next to last so that it won't be executed unless all the other steps of the clause have succeeded; as a result, it is still possible to backtrack from one clause of "g" to another. In full Prolog, but not in Turbo Prolog, we can define procedures "make_succeed" and "make_fail" that take a goal as a parameter, thus: 7 [18] make_succeed(Goal) :- call(Goal), !. make_succeed(_). make_fail(Goal) :- call(Goal), !, fail. In some implementations, "call(Goal)" is written simply as "Goal". Likewise, in full Prolog but not in Turbo Prolog we can define the procedure "once" which allows a goal to succeed exactly once, thus making any goal deterministic: [19] once(Goal) :- call(Goal), !. This procedure backtracks as much as necessary to get one successful solution to "Goal", then stops. Thus, no matter how many possible solutions there are to "f(p)", the goal "once(f(p))" will return only the first solution. If "f(p)" has no solutions, "once(f(p))" fails. Repetition through backtracking Prolog offers two ways to perform computations repetitively: backtracking and recursion. Of the two, recursion is by far the more versatile. However, there are some interesting uses for backtracking, among them the construction of "repeat-fail" loops. In Prolog implementations that lack tail recursion elimination (see below), "repeat-fail" looping is the only kind of iteration that can be performed ad infinitum without causing a stack overflow. The predicate "repeat" is built into some Prolog implementations. In most others, it can be defined as follows: [20] repeat. repeat :- repeat. (The built-in version of "repeat" should be used if available, since there are a few implementations in which the definition in [20] does not prevent stack overflow.) "Repeat" always succeeds and has an infinite number of solutions. Thus any procedure call bracketed between "repeat" and "fail" will be tried over and over again, even if it only generates one solution. For instance, the following goal displays an infinite number of asterisks: [21] repeat, write("*"), fail. The following Turbo Prolog procedure turns the computer into a typewriter, accepting characters from the keyboard and displaying them ad infinitum, until the user hits "Break" to abort the program: 8 [22] typewriter :- repeat, readchar(C), write(C), fail. The loop can be made to terminate by allowing it to succeed eventually, so that backtracking stops. The following version of "typewriter" stops when the user types a carriage return (ASCII code 13): [23] typewriter :- repeat, readchar(C), write(C), C = '\13'. If C is equal to code 13, execution terminates; otherwise, execution backtracks to "repeat" and proceeds forward again through "readchar(C)" and "write(C)". The looping in [23] can be restarted by the failure of a subsequent goal (as in the compound goal "typewriter,fail"). To prevent the loop from restarting unexpectedly, we need to add a cut as follows: [24] typewriter :- repeat, readchar(C), write(C), C = '\13', !. In effect, this forbids looking for alternative solutions to "typewriter." There is a crucial difference between "repeat-fail" loops in Prolog and repeat-until loops in Pascal. In Pascal, iteration is always accomplished by executing all the statements in the loop, then jumping from the end back to the beginning. In Prolog, backtracking may cause control to jump backward from any goal to any earlier goal that has alternative solutions. (The limiting case is "repeat", which always has alternative solutions.) Moreover, if any goal in a Prolog loop fails, subsequent goals will not be attempted. A serious limitation of "repeat-fail" loops is that there is no convenient way to pass information from one iteration to the next. Prolog variables lose their values upon backtracking. Thus, there is no easy way to make a "repeat-fail" loop accumulate a count or total. (Information can be preserved by storing it in the knowledge base, using "assert" and "retract", but this is usually a slow process.) With recursion, information can be transmitted 9 from one pass to the next through the parameter list. This is the main reason for preferring recursion as a looping mechanism. Recursion Most programmers are familiar with recursion as a means of implementing some very specialized, task-within-a-task algorithms such as tree searching and Quicksort. Indeed, Prolog lends itself well to expressing recursive algorithms developed in Lisp. What is not generally appreciated is that any iterative algorithm can be expressed recursively. Here is the classic recursive algorithm for computing factorials, expressed in Pascal and in Turbo Prolog. (Change "=" to "is" to get standard Prolog.) [25] function factorial(N:integer):integer; begin if N=0 then factorial:=1 else factorial:=N*factorial(N-1); end; [26] factorial(0,1). factorial(N,FactN) :- N > 0, M = N-1, factorial(M,FactM), FactN = N*FactM. This is straightforward; the procedure "factorial" calls itself to compute the factorial of the next smaller integer, then uses the result to compute the factorial of the integer in question. Now consider an iterative algorithm to do the same thing: [27] function factorial(N:integer):integer; var I,J:integer; begin I:=0; /* Initialize */ J:=1; while I<N do begin /* Loop */ I:=I+1; J:=J*I end; factorial:=J /* Return result */ end; In Pascal, this procedure does not call itself. Its Prolog 10 counterpart is a procedure that calls itself as its very last step -- a procedure that is said to be tail recursive: [28] factorial(N,FactN) :- fact_iter(N,FactN,0,1). fact_iter(N,FactN,N,FactN). fact_iter(N,FactN,I,J) :- I < N, NewI = I+1, NewJ = J*NewI, fact_iter(N,FactN,NewI,NewJ). Here the third and fourth parameters of "fact_iter" are state variables that pass values from one iteration to the next. State variables in Prolog correspond to variables that change their values repeatedly in Pascal. Let's start by examining the recursive clause of "fact_iter". This clause checks that I is still less than N, computes new values for I and J, and finally calls itself with the new parameters. The recursive call is the very last step in this clause, and in addition, this whole clause is placed last so that, when it calls itself, there will be no untried alternatives to be saved on the stack. This ensures that the stack will not grow during the iteration. (We will return to this point below.) Because Prolog variables cannot change their values, the additional variables NewI and NewJ have to be introduced. In Prolog (as in arithmetic, but not in most programming languages), the statement X = X+1 is always false. So NewI and NewJ contain the values that will replace I and J in the next iteration. The first clause of "fact_iter" serves to end the iteration when the state variables reach their final values. A more Pascal-like but less efficient way of writing this clause would be: [29] fact(N,FactN,I,J) :- I = N, FactN = J. That is, if I is equal to N, then FactN (so far uninstantiated) should be given the value of J. By writing this same clause more concisely in [28], we make Prolog's unification mechanism do work that would require explicit computational steps in other languages. Most iterative algorithms can be expressed in Prolog by following this pattern shown here. First transform other types of loops 11 (e.g., for and repeat-until) into Pascal while loops. Then break the computation into three stages: the initialization, the loop itself, and any subsequent computation needed to return a result. Express the loop as a tail recursive clause (like the second clause of "fact_iter") with the while-condition at the beginning. Computations to be performed after the loop terminates are placed into another, non-recursive, clause of the same procedure, which is set up so that it executes only after the loop is finished. Finally, hide the whole thing behind a "front-end" procedure ("factorial" in this example) which is what the rest of the program actually calls. The front-end procedure passes its parameters into the tail recursive procedure along with initial values of the state variables. The art of expressing iteration through tail recursion is dealt with extensively, in Lisp, in the first chapter of Abelson and Sussman (1985). Why tail recursion is special Whenever one Prolog procedure calls another, two things are saved on a pushdown stack: (1) a record of what remains to be done after return (the continuation of the calling procedure), and (2) a record of what alternative solutions remain to be tried (the alternative set). Normally, the continuation and the alternative set are represented by pointers into already existing data structures, so that it does not take any more space to represent a large set than a small one. Since every procedure call places information onto the stack, it would seem that recursion would lead inevitably to stack overflow. However, most Prolog implementations (including Turbo Prolog) recognize a special case: if the continuation and the alternative list are both empty, nothing need be placed on the stack. In this case, instead of calling itself, such a procedure can simply place new values into its parameters and jump back to the beginning of itself. In effect, this transforms recursion into iteration. A procedure that calls itself with an empty continuation and empty alternative list is described as tail recursive; the process of executing such a call without adding items to the stack is called tail recursion elimination. (The elimination of tail recursion does not mean that it should be banished from the program; on the contrary, it should be used liberally because the implementation transforms it into an efficient iterative process.) A quick way to verify that a particular Prolog implementation performs tail recursion elimination is to try the following predicate: 12 [30] test(N) :- write(N), nl, M = N+1, test(M). (Again, this is Turbo Prolog syntax; change "=" to "is" to get standard Prolog.) Start with the goal "test(1)" and see how long execution continues. If the program runs for more than 10,000 iterations, it is a safe bet that tail recursion elimination is taking place. Controlling the growth of the stack It is easy to recognize a recursive call that has an empty continuation: the recursive call is the very last subgoal in the clause that contains it. Determining whether the alternative set is also empty takes somewhat more thought. One way to get an empty alternative set is to put the recursive call in the last clause of a predicate, as in the iterative factorial program ([28], repeated here for convenience): [31] factorial(N,FactN) :- fact_iter(N,FactN,0,1). fact_iter(N,FactN,N,FactN). fact_iter(N,FactN,I,J) :- I < N, NewI = I+1, NewJ = J*NewI, fact_iter(N,FactN,NewI,NewJ). The recursive call only takes place when all other alternatives have been exhausted. The alternative set can also be made empty by using cut to rule out alternatives, as in the following replacement for "fact_iter": [32] fact_iter(N,FactN,I,J) :- I < N, NewI = I+1, NewJ = J*NewI, !, fact_iter(N,FactN,NewI,NewJ). fact_iter(N,FactN,N,FactN). Here the recursive call occurs in the first clause, but the cut guarantees that the second clause need not be considered as an alternative. 13 Because "NewI = I+1" and "NewJ = J*NewI" are deterministic, the cut can equally well be placed before them, as follows: [33] fact_iter(N,FactN,I,J) :- I < N, !, NewI = I+1, NewJ = J*NewI, fact_iter(N,FactN,NewI,NewJ). fact_iter(N,FactN,N,FactN). Note that [32] and [33] ought to be more efficient than [31]. The first clause of [31] succeeds only on the last iteration; the rest of the time, the first clause fails and control proceeds to the second clause. Thus, almost every iteration must try both clauses. In [32] and [33], the order of the clauses is reversed, so that the first clause is the one that will almost always succeed. Moreover, this clause contains a cut so that whenever it succeeds, no other clause will be tried. The result is that, in [32] and [33], only one clause -- the last one -- is tried on every iteration except the last. In actual tests using Turbo Prolog on an IBM PC, the times taken to compute the factorial of 200 were 0.58 second for [31] and 0.54 second for [32] and [33]. The gain in efficiency was small because the time saved by omitting the unnecessary test was only slightly greater than the time needed to execute the extra cut. The gain would have been much larger if the unnecessary clause had contained time-consuming computations. References Abelson, Harold, and Sussman, Gerald Jay (1985) Structure and Interpretation of Computer Programs. Cambridge, Massachusetts: MIT Press. Clocksin, W. F., and Mellish, C. S. (1984) Programming in Prolog. Second edition. Berlin: Springer-Verlag. Dijkstra, E. W. (1975) Guarded commands, nondeterminacy and formal derivation of programs. Communications of the ACM 18.8:453-457. Kluzniak, Feliks, and Szpakowicz, Stanislaw (1985) Prolog for Programmers. London: Academic Press. Turbo Prolog (1986) Version 1.0. Scotts Valley, California: Borland International. does not mean that