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