"Logal": Algorithmic Control Structures for Prolog

ABSTRACT

In practical Prolog applications, difficult and opaque uses of control primitives are often unavoidable. To relieve these difficulties, a pre1 iminary set of high-level control predicates has been developed. Two technical goals were achieved. The first was to cast control facilities found desirable in conventional languages into a logic­ programming form . The second was to provide con­ venient high-level structures for all the sorts of algorithmic routines a Prolog clause might sensibly perform. The avai labi II ty of such structures should make deliberately algorithmic use of Prolog r~spectable and may help win Prolog wider use.

INTRODUCTION

Many Prolog users accept that Prolog programs tend towards one of two extremes in a way that corresponds to two different sorts of problem. On the one hand, for many problems there are logically elegant solutions in Prolog . These require I ittle resort to "cut", "fai I" and "repeat" beyond some well structured use of "cut" in binding and final I zing clauses . Practical applIcations, however, often involve many predicates which display an algorithmic flavour, with opaque and difficult uses of "cut", "fail" and "repeat". These difficult uses of the control primitives severely disrupt the otherwise lucid self-documentation of sensibly written Prolog . This is costly, both in comprehension time and Induced errors . Regarding control faci I it ies, then, we would concur with the contention of <Hardy 1qs2> that Prolog offers only low level primitives comparable to the assembler level of conventional programming.

We assume that a much higher level of logic programming remains a relatively distant goal. Meanwhile, algorithmic programming structures are desirable both in principle and in practice. In principle, even at the program specification level, algorIthmic content Is often important. This can arise, for example, due to the relation of algorithms to time complexity. Wei !-structured algorithmic programming can thus have intrinsic self-documentary virtue. With regard to practice, prog~ammers rarely have the opportunity to rewrite, in logic programming style, routines already wei I understood in algorithmic terms, and frequently there are no elegant Prolog formulations avai I able .

There is thus a need to add to Prolog the means of wei !-structured algorithmic expression . We have been pleased to find how extensively the desirable faci II ties from conventional languages could be incorporated without damaging Prolog. This report presents our first Implementation of the "Logal" control structures, which run on the PDP-11 UNIX Prolog system, version NU7, as sketched in appendix F of <Ciocksln and Mellish 1qsu.

D. C. Dodson

A. L. Rector

Department of Community Health University of Nottingham Medical School Queens Medical Centre Nottingham NG7 2UH U.K.

II A GENERALIZED LOOP CONSTRUCT

Our offering comprises two programming constructs, a conditional and a generalized loop . The loop is the more innovative and important of these. It follows the practice of languages such as ALGOLbS In having a "bui I ding block" syntax for loops. The following fixed-order sequence of four optional "building blocks" or "phrases" is used .

<for-phrase>

<while-phrase>

<do-phrase>

<until-phrase>

[generator of I nstancesJ Cexit test before main bodyJ ["main body" of loop]

Cexit test after main body]

Each of these phrases consists of an appropriate keyword followed by a predicate to be cal led, for example "while read line(U" or "until X=Y" . We have allowed ourselves two arbitrary restrictions on the selection of phrases. First, a loop cannot consist of awhile-phrase or until-phrase alone . Second, no loop can include both a while-phrase and an unti !-phrase. Whatever selection of phrases is made for a given loop, the phrases are executed in the order In which they appear, repetitively, unti I a termination condition arises . Adaptations of the conventional loop necessary to suit the Prolog environment are detailed below . Distinctive keywords are used to signal modified semantics .

Our keywords are declared as operators so that the phrases can be concatenated with a minimum of parentheses. This technique makes an additional mandatory closing keyword useful to avoid ambiguity and help catch syntax errors. We use "od" In this role for loops . Relying on avai I able syntactic fac iIi ties has meant that parentheses are st iII required around arguments whose top level operator has a priority equal or greater than that of the keywords, as in the following.

do < p1, p2 > unt i I p3 od do < do p1 until p2 od >until p3 od

We have not initially provided for-phrases generating number series . Rather, after the style of "every" in Icon <Griswold et. al. 1q91) a series of outcomes Is generated by calling a predicate and then repeatedly backtracking and resatlsfying it until It fails. To signal this we write the for­ phrase In the form "for each <term>". "for each" conveys the notion "for-each instantiation-of" concisely and naturally. Generating arithmetic series Is reasonably easy with this arrangement .

The next adaptation is fundamental to the semantics of loops In the Prolog environment. It concerns the action to be taken If, on any cycle of iteration, the main body of the loop (i.e . the do-phrase> should fall. Two alternatives have been provided . Loops with do-phrases introduced by the keyword "do_any" succeed regardless of any cycles of Iteration In which their body falls. Loops with do-phrases Introduced by the keyword "do_one", however, fall immediately should their body once fall. For example, If the predicate:

for each rule<R> do_one < translate<R,RT>, store<RT> > od

succeeds, then for each rule a translation has been found and stored . "for each G do one Pod" In fact equivalent to the well known construct "not < G, not P )". The "do_one" form is in fact the general case, as "do_any X" is equivalent to "do one <X ; true )" . The "do_any· option is provided for convenience and efficiency . Loops which Include a "do_one" phrase and a "while" or ·untl I" phrase incur overheads in distinguishing between two modes of termination, whereas the corresponding "do_any" loops do not .

The syntactic I imitations of the Prolog interpreters we use require a final adaptation. Special treatment Is required for phrases which are sometimes but not always the first phrase of a loop. For Instance, when a for-phrase precedes a do-phrase, the do-phrase is not the first phrase in a loop, thus its first keyword has to be a dyadic Infix operator. When a do-phrase is the first phrase In a loop, however, its first keyword must be a monadic prefix operator. This in turn requires the use of distinct keywords. Fortunately, when a loop begins with a do phrase, It is natural to say "repeat" instead of "do", as in Pascal. Likewise, we use "repeat_one" instead of "do_one~ a~d "r epeat_any" instead of "do_any" in this context . This produces structures such as the following.

repeat_one P until U od repeat_any P od

Neither for-phrases nor unti !-phrases can appear in both monadic and dyadic contexts, leaving the case of the while-phrase. At the start of a loop, we Introduce awhile-phrase with plain "whl le", but use "whi le_stl II" otherwise, as shown below.

while W do_any Pod for_each G whlle_stil I W do_one Pod

The complete implementation of the general I zed loop is given in Appendix I. This includes a clause for each format of loop that can be constructed using the above rules. Although there are 15 such c I auses at the top I eve I, thIs does not amount to a great deal of code . However, much of this code Is excruciatingly difficult to write and read, underlining the ergonomic difficulties presented by the control primitives . The following relatively simple case illustrates something of this.

repeat_one P until repeat, u od :- I, detval <P,V>, /1 set V to success of P 1/ < not V ; determine<U> >, I, V, I. /I whether the loop succeeds 1/

where

determl ne<X> :- call to<X>, ! . /I a call that /1 can't be backtracked into from outside 1/

detvai<X,true> :- callto<X>, I. /I call X I/ detval <X, fall> :- I. /1 "determlnately" and /1 advise whether It succeeded 1/

call to<X> :- X. /I unit ke the system "call· /1 predicate, a real call to fall back /1 to In case X executes "1, fail" . I/

This works as follows . "repeat· always succeeds, so every time the loop is to be repeated, control wl I I backtrack to this point and work forwards again. "detval" is then used to call P and according to whether or not P succeeds, set V to true or fai I. Now, provided V=true, a cal I wi I I be made to U. If e 1 ther V=fai I, or V=t rue and the call to U suc­ ceeds, the loop must terminate . All this is handled by < not V ; determlne<U> ) . If this fai Is, control backtracks to the repeat for the next iteration. If it succeeds, a cut is then passed which throws away the backtrack history of the cal I to the loop. The final call to V fails the loop if the body of the loop, P, failed.

In general, variable bindings made In a phrase which succeeds rema in in scope for all subsequent phrases within a cycle . In the clause above, for instance, "de tva I <P,V>, < not V ; determine<U> )" ensures that variable bindings from successfully calling P remain in scope when calling U. Writing "( not P ; determine<U> )" would not achieve this. At the end of each cycle, a! I variable bindings are undone ready for a further cycle, unless iteration is terminated by a while-phrase or until-phrase . After termination by a while-phrase or until-phrase, all bindings made in the last iteration remain in force. These rules are quite natural; they were formulated only after we had exploited them for some time. When not required, variable bindings introduced by a cal I are easl ly discarded by surrounding the call with a double "not". <Variable bind ings, or instantiations, represent existence . For any set of variables, their concurrent instantiations <those currently In scope> are things of which the successfully called predicates ment ioning them are true.)

III THE CONDITIONAL CONSTRUCT

Apart from loops, two other high-level lntramodular control structures are conventionally recognised, the conditional and the case structure. A case structure suggests a dir ect access control step . Such a step cannot be programmed within a Prolog clause, though some interpreters provide it in the form of indexed clause selection. We use the following predicate for conditionals . It is an extension of a "cond" predicate described In <Bundy and Welham 1977>. The operator declarations Illustrate the technique used in both constructs.

Recursive application of the else_lf_any option allows ease-l Ike structures . Note that backtracking through antecedents is prevented whilst backtrack­ ing through selected consequents is unhindered.

IV EXAMPLE OF USAGE

This example is chosen to i I lust rate recursive application of the loop format discussed In detail above, rather than for elegance or even real ism. It repeatedly performs a "consultation". After each consultation it repeatedly asks the user whether another is desired until it gets a valid reply. " read_line" obtains a line of input and returns it as a l ist of symbols .

top loop repeat_one ( consultation, /1 whatever this is 1/ write< 'Care for another consultation'') ) unti I ( /I f i rst ensure a valid response : I/ repeat_one read_llne<CHI_J) /1 use first unt i I ( /1 word of user 's response 1/ if any not < pos_ans<H> Then ( neg_ans<H> fi od , write<'Sorry, would you like ' ), write<'another consultation''), nl, write<'say y <yes> or n <no> : '), fa i 1 ) neg_ans<H> /1 finish if neg. response : 1/ ) od . pos_ans<y>. pos_ans<yes> . neg_ans<n> . neg_ans<no> .

V CONCLUSIONS

Extensions to the syntactic faci I I ties of Prolog interpreters would a l low certain improve ­ ments and might be of wider interest . If binary prefix operators were allowed, keywords could be defined as "fxy" operators of equal dominance, and distinctions such as that made between "while" and "whlle_stil I" could be dropped. Some arrangement to eliminate the remaining uses of parentheses around control predicate arguments may also be practical .

The generalized loop could be further refined. The option of writing for-phrases generating number series in the conventional manner would be an added conven ience . More radically, it may be better to extend the the building block approach to allow an arbitrary sequence of do-phrases and loop termination phrases, optionally preceded by a for-phrase, using recursive definition along the I ines employed here in the conditional construct .

We have identified the sorts of Intra-modular control constructs that can usefully be programmed In Prolog and developed structured ways of writing them. The two constructs have been in regular use in substantially the form presented since last August . Appendix I defines the current implement­ ation. We find the Logal constructs of great value in develop ing medical decision support systems. We hope they wi I I make the mixed use of algorithmic and logic programming within Prolog more open and respectable, and help gain users for whom the language might otherwise seem too exotic . We would be interested to know of possible improvements .

ACKNOWLEDGMENl'S

Special thanks are offered to alI contributors to the excellent UNIX implementation of Prolog at Edinburgh and to J . B. Brooke whose critic i sm of Prolog prov ided the stimulus for this work.

APPENDIX I

Together with the de tva!, determine, ca ll to , and lf_any predicates given above, the following predicates for the generalized loop and for error detection complete the Logal package. 1 -op<150,fx,for_each). '-op<150,fx,repeat_any>. '-op<14B,xf,od). 1 -op<147,xfx,while_stifl). 1 -op<145,xfy , do_any> . 1 -op<150,fx,while> . 1 -op<150,fx , repeat_one> . 1 -op<14b,xfx,unti I> . '-op<145,xfy,do_one) . for each G while stilI W do one Pod :- ! , · -for_each_whiTe_do_x<G,I(P>, !, do_true, !. for_each G while_sti I I W do_any Pod :- ! , < G, detval <W,V>, < not V ; determine<P>, fai I ; true ) , ! . for each G while sti I I W od ! , < G, not W ;-true ), ! . for each G do one P unti I U od ! , < G, detvai<P,V>, if_any not v then assert(do one failed) else determine<U> fi ; true ) , ! ; do-true, ! . for each G do_any P-until U od : - !, < G, detval <P, ) , determine<U> , true ) , ! . for each G do one Pod :- !, not< G, not P ) . for-each G do:any Pod : - ., , < G, determine<P>, fail; true),! . for each G unt i I U od :- ! , < G, determine<U> ; true ), ! . for each God:-!, < G, fail ; true ), ! . for=each X :- bad_format<for_each). while W do_any Pod :- ! , repeat, detval <W,V), < not V ; determine<P>, fa i I ) , I. while w do one Pod : - ! , for _each_while_do_x<repeat,W,P>, !, do_true, !. while X :- bad_format<whi I e) . repeat_one P until U od :-!,repeat, detvai<P ,V> , < not V; determine<U> ), ! , V, ! . repeat_one X od :- I, repeat, not X, ! , fai I . repeat_one X : - bad_format<repeat_one) . repeat_any P until U od :- ! , repeat, detval <P,Vl , < not V ; determine<U> ) , ! . /lrule except ionl/ repeat_any P od :- ! , repeat, not <P>, ! . /I do . 1/ repeat_any X : - bad_format<repeat_any> , for each white do x<G,W,P> : - G, detvai<W,V), -( no1 V; not-P,assert<do one failed); fail) . for_each_whi le_do_x<X,Y,Z) . - - do_true :-not retract<do_one_failed) . bad format<X> :- nl, write('bad ' ) , write<Xl, - write( ' format ' ), bug . bug : - nl, backtrace, break.