Otherwise

Appeared in Volume 8/3, August 1995

Does anyone know what the the "otherwise" statement does in Quintus? I assume it has something to with conditionals, but am not sure how to substitute for its behavior in a non-Quintus environment (C-Prolog).

ok@goanna.cs.rmit.edu.au
Richard A. O'Keefe
17th February 1995

It is explicitly stated in the Quintus manuals (see for example page L-184 in the Reference section of the 3.1 manual) that 'otherwise' is identical in every respect save spelling to 'true'. I don't know who was responsible for what I consider the silliest addition to QP; someone thought it was a good idea to write:

( a -> b
; c -> d
; otherwise -> e
)

( a -> b
; c -> d
; e
)

Kutnar writes:
I assume it has something to with conditionals, but am not sure how to substitute for its behavior in a non-Quintus environment (C-Prolog).

The best way is to eliminate it entirely. It is never necessary in QP.

The easiest way to cope is to add the rule:

otherwise :- true.

fjh@munta.cs.mu.oz.au
Fergus Henderson
23rd February 1995

Richard A. O'Keefe writes:
... NU Prolog ... interprets a solo (a -> b) as (a -> b ; true) - a truly strange, not to say dangerous, choice

You can certainly call it dangerous, but I don't think it's fair to call it strange. NU-Prolog's meaning is the one you would expect for mathematical implication (except that it doesn't delay). The standard Prolog meaning could equally well be described as strange, since it uses a standard mathematical symbol in a non-standard way.

ok@goanna.cs.rmit.edu.au
Richard A. O'Keefe
24th February 1995

The reason I can call it dangerous is that it takes syntax that other Prologs use for one construction, and gives it a different semantics. To give a very similar example, C uses infix "^" for bitwise exclusive OR, while a number of languages with syntax deliberately and extensively copied from C (notably AWK and New S) use the same symbol to mean raising to a power (exponentiation).

I think the cases are parallel in another way as well. In both the Prolog/NU Prolog and the C/AWK,S cases - the original language designers made a choice which could reasonably be challenged, but which was consistent within its own scope. People designing subsequent languages deliberately copied the earlier language, but they changed one or two things to suit their own taste - the earlier usage is still numerically dominant.

As for whether the choice is strange or not, it is important to remember where Prolog got its syntax in the first place. Prolog borrowed a lot from Pop-2 and Lisp. In particular, anyone who read the Lisp 1.5 manual will remember the M-lisp syntax [c1->t1; ... cn->tn] for conditionals. Edinburgh Prolog makes use of two kinds of arrows, and one of them is logical and the other one isn't. The arrow which is related to logical implication is :-, so that (A :- B) is to be read as B => A. The arrow which is NOT related to logical implication is ->. I do not read A->B as a logical implication in Prolog. I never have done. I have never felt any temptation to. Complaining that P->Q in Prolog does not act like logical implication is like complaining that P,Q doesn't concatenate vectors (which it does in APL). It was never supposed to.

Let's look at this another way. When p, q, and r are pure predicates with no arguments (propositional letters), then:

( p -> q ; r )

has the logical force of:

( p AND q ) OR ( NOT p AND r )

That is, in this construct, which NU Prolog shares with other Prologs, the right arrow does not have the force of a logical implication. If the right arrow in this situation did have the force of a logical implication, the reading would be:

( NOT p OR q ) OR ( r )

This of course brings out the point that if someone does want a sort of crippled implication in Prolog, they can write:

implies(P, Q) :- \+(P).    % better to use sound negation if you have it
implies(P, Q) :- Q.

(P => Q) :-
  assert(P, Ref),
  ( call(Q) -> erase(Ref) ; erase(Ref), fail ).

harald@cs.mu.oz.au
Harald Sondergaard
25th February 1995

Richard O'Keefe wrote:

As to abuse of mathematical notation, I'm afraid there is no standard mathematical notation for implication. Most of the books on my shelves use a double-shafted arrow or a horse-shoe, certainly none of them use a minus sign followed by a greater than.

As Richard indicates, there are two issues here.

(1) Is there a standard sign for material implication?

My feeling is that Peano's horse-shoe is dying, and Hilbert's single-shafted arrow is winning. (This is good because Peano's notation clashes with standard notation in set theory.) I had a quick browse through the books on my shelves, and a clear majority use the single-shafted arrow, the exceptions mainly being older books. Quine, who has always been extremely concerned with the importance of well-chosen notation, at some stage made a decision to abandon other signs for material implication and take up Hilbert's. While it is true that there is no standard, I believe that current practice favours single-shafted arrow.

(2) Is `->' a single-shafted arrow?

It is natural to assume that the `minus sign followed by a greater than' tries to approximate a single-shafted arrow. Experience shows this: If not told otherwise, practically anybody who is being introduced to logic programming assumes that in:

q :- (p -> p).

`->' stands for material implication (no matter what it stands for in imperative or functional programming languages).

My conclusion is that Prolog's usage of `->' is discordant with common usage, and we may as well admit it.

ridoux@calypso.irisa.fr
Olivier Ridoux
24th February 1995

Richard A. O'Keefe writes:
Edinburgh Prolog makes use of two kinds of arrows, ...

As to abuse of mathematical notation, I'm afraid there is no standard mathematical notation for implication. ...

In The Art of Prolog the arrow which is related to logical implication is a single-shafted arrow (pointing to the left). In Prolog II, it is also a single-shafted arrow (pointing to the right). In this last case, the arrow is meant to recall of the rewriting mechanism that interprets implication. In The Handbook of Theoretical Computer Science (Van Leeuwen, eds), the chapter on Logic Programming by K. Apt uses a single-shafted arrow for object-level implication (program level), and a double-shafted arrow for meta-level implication (discourse level). The single-shafted arrow is used in either direction, but it always points from the premises to the conclusion. The chapter on Logics of Programs by D. Kozen and J. Tiuryn uses the same notation. In the same book, single-shafted arrows may denote function domains, function type, rewriting, derivation, pairs, guarded statements, etc. It may also be decorated in various ways. The double-shafted arrow denotes implication, multi-step derivation, and a type-related relation.

Still, I am not happy with the standard Prolog meaning for (C->A). Seeing no logic in (C->A;B) I would like to read it as a conditional statement as in a procedural language (if C then A else B). In these languages, (if C then A) usually means (if C then A else skip). It seems to me that 'skip' is simply much more close to 'true' than to 'false'. So (C->A) should denote (C->A;true).

conway@munta.cs.mu.oz.au
Thomas Charles Conway
24th February 1995

Indeed (C -> A; B) should have the same behaviour as (C,A ; \+C,B) for it to do otherwise it pretty marginal in terms of semantics. Of course, when you write the ->; notation, the compiler should optimise the execution of course (using a soft cut not a hard cut as standard Prolog does).

NU-Prolog has (if C then A else B) which has this more defensible behaviour as well as (C -> A; B) which has the usual behaviour.

bowers@cs.bris.ac.uk
Antony Bowers
24th February 1995

Olivier Ridoux writes:
Still, I am not happy with the standard Prolog meaning for (C->A)...

While it may be difficult to see the logic in Prolog's (C->A;B), there is no difficulty in giving a logical meaning to conditionals of the form (if C then A else B). The meaning is (C & A) \/ (~C & B). This idea was introduced by Lee Naish in NU-Prolog. There is no need to think of conditionals purely procedurally.

Goedel has this form of conditional, and it is very successful in that it almost completely eliminates the need for explicit pruning, while remaining entirely declarative. There is a more powerful version with existential quantifiers available.

One problem with (A->B) in Prolog is that declaratively it is just conjunction, and it seems rather pointless to use the arrow just to conceal a one-solution operator. In Goedel one would write ({A} & B) to achieve the same effect, where {A} means "find one solution for A".

In Goedel (IF C THEN A) means (C & A) \/ ~C, and this seems natural to me, probably by analogy with imperative languages as Olivier Ridoux suggests. Let me be the first to point out that this construction is nowhere near as useful as might be expected, and it is difficult to find any convincing examples. Here's an attempt:

PREDICATE MemberCheck : a * List(a).
MemberCheck(x, [y|ys]) <-
 IF x ~= y
 THEN MemberCheck(x, ys).

Languages that enforce safe negation and lack an explicit cut operator are so much easier to understand than Prolog (and consequently much nicer to teach).

fjh@munta.cs.mu.oz.au
Fergus Henderson
25th February 1995

Goedel's (and NU-Prolog's) if-then-else is pretty successful as a declarative replacement for Prolog's (C->A;B). Unfortunately, it's not successful in doing so while retaining efficiency.

The problem is that in both Goedel and NU-Prolog there is a run-time check to see whether the non-local variables in the condition are ground. This check is linear in the size of the terms to which those non-local variables are bound. In real-world programs, situations where those terms are very large arise frequently. The net implication of this is that Goedel programs (or pure NU-Prolog programs) tend to run slower than corresponding Prolog programs by a factor which is asymptotically proportional to the amount of memory the program consumes!

Mercury solves this problem, because Mercury's compile-time mode checking ensures that the run-time check isn't necessary.

conway@munta.cs.mu.oz.au
Thomas Charles Conway
25th February 1995

The example which Fergus and I both know well is in the Mercury compiler itself which we bootstrapped from NU-Prolog. To start with we used NU-Prolog's (if then else) construct for safety, and later, once the mode analyser was working, we replaced it with ( -> ; ) since the compiler's checking would ensure that our programs were not unsound. When we did this (and replaced (not G) with (\+ G) for the same reasons), performance went up dramatically. We were frequently passing in the compiler's main data structure which was ground, and megabytes in size.

Of course, one of the problems with using ( -> ; ) is that it puts a hard cut after executing the condition, so that if the condition were to produce multiple solutions these would be pruned. The Mercury ( -> ; ) only prunes the else goal when the condition succeeds, so the ( -> ; ) construct as a whole can output multiple bindings that were produced in the condition.

rss@seg.npl.co.uk
Roger Scowen
23rd February 1995

Richard A. O'Keefe writes:
... NU Prolog ... interprets a solo (a -> b) as (a -> b ; true) - a truly strange, not to say dangerous, choice

Fergus Henderson replied:

Well, you can certainly call it dangerous, but I don't think it's fair to call it strange. NU-Prolog's meaning is the one you would expect for mathematical implication (except that it doesn't delay). The standard Prolog meaning could equally well be described as strange, since it uses a standard mathematical symbol in a non-standard way.

ISO/IEC 13211-1 (Prolog -- Part 1: General core) defines a goal:

(If -> Then)

as failing when If fails. This decision was taken so as to (1) be compatible

with existing Edinburgh Prolog systems, and (2) fit in with the notations:

(Either ; Or)

and:

(If -> Then ; Else).

ISO/IEC 13211-1 defines the built-in predicate true/0, but not the built-in predicate otherwise/0.

fjh@munta.cs.mu.oz.au
Fergus Henderson
25th February 1995

Just to clarify my position a little - I think the Prolog committee certainly made the right choice. But life would have been easier if the Edinburgh people had chosen a different syntax in the first place, such as (if ... then ... else ...) or (If ? Then : Else).

bhogan@bedlam.rahul.net
Bill Hogan
26th February 1995

I think the key distinction is between goals which succeed at least one way and goals which never succeed.

Let the effect of `!+' in a rule be to prevent the Prolog processor from finding in the current rule any answers in addition to any it has found at the point the `!+' has reached, but without excluding from consideration any remaining clauses in the current set of clauses.

Let the effect of `!-' in a rule be to exclude from consideration any remaining clauses in the current set of clauses, but without preventing the Prolog processor from finding answers in the current rule in addition to any it has found at the point the `!-' has reached.

Now consider the following sentence-pattern:

P :- Q,R. P :- not(Q),S.

If I wished to spare the expense of seeking a first solution to Q twice, I could write:

P :- Q,!-,R.
P :- S.

P :- if_(Q)_then_try_(R)_else_try_(S).

is as follows:

ever succeeds?

Q	R	S	if_(Q)_then_try_(R)_else_try_(S)
yes	yes	yes	yes, according to R, given Q.
yes	yes	no	yes, according to R, given Q.
yes	no	yes	no
yes	no	no	no
no	yes	yes	yes, according to S.
no	yes	no	no
no	no	yes	yes, according to S.
no	no	no	no

P :- Q,!-,R.
P :- S.

P :- Q,R.
P :- not(Q),S.

Roger Scowen writes:
ISO/IEC 13211-1 (Prolog -- Part 1: General core) defines a goal:

(If -> Then)

as failing when If fails. This decision was taken so as to (1) be compatible

with existing Edinburgh Prolog systems, and (2) fit in with the notations:

(Either ; Or)

and:

(If -> Then ; Else).

(1) is a very good reason. The logic of (2) is not clear to me as either choice would "fit in" with these notations.

Fergus Henderson writes:
But life would have been easier if the Edinburgh people had chosen a different syntax in the first place, such as (if ... then ... else ...) or (If ? Then : Else).

Agreed, though even if-then would have confused many people. The chosen syntax confuses people due to the connection with "if-then-else" which is unavaoidable, but also with logical implication. People think that Prolog is based on logic and therefore -> is based on logical implication. We certainly thought that in Melbourne when MU-Prolog was designed and (very unfortunately) were still had that misunderstanding when NU-Prolog was implemented (otherwise we would have changed). Of course -> was not based on logical implication. Prolog was designed as an AI language and naturally borrowed various ideas from other AI languages, notably the conditional construct of LISP. An unfortunate choice, I think, but not at all unreasonable.

sverker@sics.se
Sverker Janson
7th March 1995

Fergus Henderson wrote:

The problem is that in both Goedel and NU-Prolog there is a run-time check to see whether the non-local variables in the condition are ground.

For the if-then-else to be quite sound in a language such as AKL, it is only necessary that the condition is executed quietly, i.e., without binding non-local variables. It is very, very cheap to check that no such bindings have been produced (by examining the trail). Couldn't this also be applied to (suitably generalised versions of) Goedel and NU-Prolog?

lee@munta.cs.mu.oz.au
Lee Naish
20th March 1995

That is essentially what the original IC-Prolog did. There are two problems: 1) what do you do if variables were bound (IC-Prolog aborted the execution) and 2) what do you do if the negated call has an infinite number of solutions. Some options were discussed (and more or less rejected) in my thesis:

Lee Naish, 'Negation and control in Prolog'
LNCS, Springer-Verlag, 238, 1986, pp.119

Given that what I want is a logically sound version of if-then-else in Prolog, no more (i.e., dynamic scheduling), no less (i.e., having its uses limited by groundness tests), I would (1) like the system to complain when a condition is noisy, (2) do nothing about infinite numbers of solutions. What does your thesis say about this (apparently IC-Prolog-ish) option?

lee@munta.cs.mu.oz.au
Lee Naish
31st March 1995

It's not that IC-Prolog-ish since one of the main feature of IC-Prolog was its coroutining features (I assume that's what you mean by "dynamic scheduling"). My thesis doesn't really address your question, but take a look at:

Lee Naish, 'Negation and quantifiers in NU-Prolog'
Proc. of the 3rd Int. Conf. on LP, London, England
July 1986, Ehud Shapiro (ed.),
LNCS 225, Springer-Verlag, pp.624--634