Optimistic if-then-elses
Miguel Calejo
Technical Note, GPLIA/DI/FCT/UNL, July 1989
(draft)
Abstract
We explore the possibility of regarding the "if-then-else"
constructs in Porto's "UNL Prolog" (UNLP) as logical
if-then-elses. If-then-elses in UNLP are represented via predicate
definitions containing clauses with commitments or "exclusive
implications".
Avoiding a major reimplementation, which would require
sophisticated features typically absent from the standard Prolog
implementations we'd like to use, does impose some restrictions.
Basically, we must ensure that program computations stay away
from situations where a Prolog (cut-based) if-then-else would
be computed erroneously, therefore adopting an "optimistic"
stance - i.e., hoping that such situations can be avoided naturally.
We look into some program examples and conjecture that the restrictions
are reasonable, although experimentation is strongly needed.
The operational behavior being different from UNLP,
we rename this as UNLP' and propose a simple implementation, based
mostly on a small change to the Prolog cut.
Finally we overview some potential benefits of UNLP',
regarding intelligent backtracking, debugging, parallelism. We
also enumerate some applications where the optimistic if-then-else
is too restrictive(??), and raise some (open) questions.
A final warning: this document pretends solely to
evangelize persons on the importance of this line of work (to
be done) and its problems, not to solve them!
Introduction
It's already part of the UNLP folklore the (polemic!)
statement that "UNLP clauses have a more declarative reading"
or "are more logical", or at least "are more readable",
relatively to Prolog. Here we attempt to force this statement
to be true, and do believe we succeed, although this depends on
a different operational behavior of the UNLP implementation, which
we (re)name UNLP'. We're actually trying to strengthen UNLP by
going back to its roots ([Porto 85]), in an attempt to structure
Prolog to have programs with better properties: increased readability
of course, but also efficiency and power for the language and
its programming tools.
We concentrate exclusively on the if-the-else problem,
and leave out all issues regarding actions, parallelism
and program structuring (CxLP, etc). In other words, we're
considering purely deductive sequential computations over "flat"
programs, hoping that the results will apply more or less transparently
for other extensions.
UNLP if-then-else reviewed
We'll review both the declarative and operational
semantics for it by using a small predicate definition example:(1)
p(X,Y) <-> a(Z,Y) <= c(X,Z).(2) p(X,Y) <- b(X,Y).
Sometimes below we'll refer to c(X,Z) as the "condition",
a(Z,Y) as the "then" branch, and b(X,Y) as the "else"
branch.
Declarative semantics
It is generally accepted that the declarative semantics
for a UNLP predicate definition as above is that of an if-then-else.
Borrowing it from [Porto 85, p. 67]:
p(X,Y) ´
|c(X,Z) Ÿ
a(Z,Y)| /
|¬c(X,Z)| Ÿ
b(X,Y)
The "|" brackets denote the scope of the
implicit existential quantifiers, in this case affecting variable
Z. We're considering the equalities introduced in the head unification
process, whatever they might be, to be included in the condition.
Operational Semantics
The UNLP operational semantics is defined using the
Prolog cut:p(X,Y) :- c(X,Z),
!, a(Z,Y).p(X,Y) :- b(X,Y).
How far is this from a correct operational semantics
for if-then-else ? In [Porto 85, pp. 67-80] three possible operational
semantics are defined for if-then-else, suggesting three different
implementations. The reader may refer there for additional details,
we'll simply repeat here the main ideas and we'll expand a little
below as we stick to our choice.
First, the "correct" operational semantics,
obtained computing accordingly to the declarative semantics. Second,
the "larger" semantics, which essentially may omit
the negative literal c in the second disjunction branch above,
and may therefore be unsound. Third, the "smaller" semantics,
ignoring the second branch whenever c has a true instance, which
therefore may be incomplete.
It turns out that UNLP follows neither of these three
semantics! Given the absence of a precise declarative semantics
definition, one might believe that its operational semantics would
be the "smaller" semantics, the one closer to Prolog's
if-then-else, which directly supports UNLP… However, for
situations where the condition c above has more than one true
instance, the UNLP operational semantics is "twice"
incomplete: not only is clause (2) prevented to be used, as in
the "smaller" semantics, furthermore irrespective of
the bindings that c may illegitimately produce; but c is prevented
from producing additional solutions, whose (legitimate) bindings
to Y might support additional solutions for p.
This computational behavior originates in the Prolog
cut: once reached, it not only prevents additional clauses to
be used, but also prevents backtracking into the (left) brother
goals. We'll now define a new operational semantics for UNLP -
UNLP'- to implement if-then-else "correctly", by sticking
to good use of the "smaller" semantics.
UNLP': the optimistic if-then-else
The correct operational semantics is hard to implement
(cf. [Porto 85]), as it involves goal delaying among other things.
An interesting possibility consists in taking either the "larger"
or "smaller" semantics, and join it with some mechanism
to check if, for each particular computation, the chosen operational
semantics coincides with the correct one - therefore taking the
optimistic stance that such computational situations can be made
to occur naturally most of the time. This mechanism may then notify
the programmer whenever an incorrect use arises. In a way, the
whole system now implements a "correct" operational
semantics, in the sense that it is aware of when it doesn't!
The "greater" operational semantics looks
a bad candidate, as it implies checking the goal variable bindings
to decide whether or not to use the "else" branch -
and this independently of checking if it coincides with the correct
semantics for each particular situation. One of our objectives
being an implementation closer to standard Prolog features, we'll
turn to the "smaller" semantics instead. We'll start
by defining the situations where this semantics coincides with
the correct one.
On when correct="smaller" operational
semantics
We'll now enumerate the relevant situations that
may occur when calling the example predicate p above. Let V be
the set of variables in the goal call to p.
c fails without solutions
The second clause is tried - the "smaller"
semantics is used correctly.
c succeeds, always without binding variables in
V
Therefore introducing no constraints on variables
in V - the "smaller" semantics is used correctly.
c succeeds binding some variable in PV
In general, the "smaller" semantics
incorrectly prevents the second clause to be used. There's an
exception: if we're sure that no other clauses match the goal.
We'll get back to this point below, when describing split unification.
In conclusion, to ensure that the "smaller"
operational semantics implements the correct declarative semantics
we must forbid bindings to the goal variables during the evaluation
of conditions.
Implementation
"Smaller" operational semantics
We now present two implementations for the smaller
operational semantics. As said, before, using the Prolog cut directly
is not enough. We'll define how to translate clause (1) above
( p(X,Y) <-> a(Z,Y) <= c(X,Z) ).
Using a nonlogical variablep(X,Y)
:- create_counter(Flag), % Flag:=0 ( true; get_counter(Flag,1),
!, fail), c(X,Z), set_counter(Flag,1), a(Z,Y).
Flag is a "counter", as supported by ALPES
Prolog. This solution is obviously uninteresting, except perhaps
to perform some experiments, as most programs tend to use if-then-elses
extensively.
Cut with flagp(X,Y)
:- c(X,Z), soft_cut, a(Z,Y).
This depends on a different cut built-in, "soft_cut",
that implements the operational behavior in the previous paragraph:
if c has a solution, on failure of c the remaining clauses for
p are not tried. It involves having a flag associated to each
choicepoint, expressing whether it should or not be considered
on backtracking. Notice that in a typical WAM the soft_cut must
not remove choice points from the top of their stack, as
the choicepoints for the computation below c must be preserved
(except of course if c introduces no choice points).
Checking mechanism
The checking mechanism must verify, for each goal,
that its variables are not bound during the evaluation of conditions
in matched clauses. If all computations actually computed in a
program verify this, we say the program is UNLP'-correct.
Dynamic checking
Extensive dynamic checking seems both too expensive
and not very important. Too expensive because all free variables
in each goal must be watched during evaluation of a condition.
An elegant solution may exist, but we guess that it would involve
some important change to a WAM (certainly more drastic than to
implement soft_cut!).
Anyway it doesn't seem very important to check these
bindings always: many large programs have been written
in UNLP, and at least their authors believe that the respective
operational behavior usually coincides with the intended (correct)
semantics for if-then-else. Good Prolog programmers tend to write
declaratively, but always with an eye on operationality…
Dynamic checking seems more adequate during execution
under a debugger, by explicit user request. Detecting a "wrong
binding" would allow a (say, algorithmic) debugger to help
pinpoint the source of error, maybe treating the problem as a
variant of the "inadmissible goal" bug manifestation
case.
Remember however that some bindings may be legitimate
- as when no additional clauses can match the goal - and must
be dealt with specially. Many such situations could be dealt with
simply by checking if the current goal has a choicepoint (and
therefore relying on the Prolog implementation's indexing mechanism);
others may need more attention.
Static checking
On the other hand, static analysis seems more promising.
For example, if one concluded that a predicate was always called
with a free variable as argument, deemed to match a functor in
the head of a clause with condition, then the program would be
"incorrect".
Work on mode analysis, abstract interpretation, etc.
should be of use here.
UNLP auxiliary predicates
Some meta-predicates can no longer be defined in
the base language (UNLP'), but must be considered as additional
primitives. For example, "once G" must be regarded as
what it is - an "action", or a "command",
but certainly not a predicate.
This falls out of this document's purer logic programming
scope, and must be studied separately, probably along the lines
of [Porto 83].
The need for split unification
We now recall a UNLP feature seldom used, but which
may become necessary: split unification [Porto Pereira
Trindade 87]. It allows marking of some terms in a clause head
(the "initial" terms), to be unified before evaluation
of the condition; the remaining terms in the head are to be matched
against the goal only after the condition. We'll use a
different notation here - underlined instead of curly brackets.
For example, in:append([X|A],B,[X|C])
<-> append(A,B,C) <= true.append([],L,L).
the first clause can be regarded as syntactic sugar
for:append([X|A],Y1,Y2) <->
append(A,B,C) <= Y1=B, Y2=[X|C].
Failure to consider the splitting information would
certainly cause a naïve checker to detect a "correctness
violation": typically the third argument in a call to append
is a free variable, to become bound to the list ! However, if
one's sure that the following clauses won't be used, as is typically
the case for append, the binding to the third argument is
legitimate. In other words, if one's sure to call append with
the first argument bound then the split unification declaration
is superfluous.
The append case then goes without split unification… but
in general, enforcing UNLP'-correctness may require it. This example
also raises the need for non-naïve checkers, that not only
check bindings to the goal's variables but also check whether
additional clauses may match it.
Trying UNLP'
In this section we speculate on whether the UNLP'-correctness
condition and the soft_cut are too restrictive. Only practice
will tell, but meanwhile we examine a few cases to see what happens.
A meta-interpreter
Is UNLP' too restrictive to write a meta-interpreter
? Not if we use a different metapredicate, for example (cf. [Calejo
89] for more details and options) one which gathers predicate
definitions as a whole instead of one clause at a time.
The main interpreter step:i(G)
<-> predicate_definition(G,Rules), i_body(Rules,G).% Rules
is a list of clause types and references
i_body( r(iff,R)._, G ) <-> i(B) <= rule(R,G,C,B), i(C).i_body(r(if,R)._,G)
<- rule(R,G,B), i(B).i_body(_.Refs,G) <- i_body(Refs,G).
As the first argument to i_body is always bound when
calling it, the UNLP' correctness condition is preserved by the
meta-interpreter (and may be violated by i(C) as it should!).
Negation as failure
The usual "not" metapredicate can be easily
implemented:not G # <= G.
% cf.UNLP: same as not G <-> fail <= G.not _.
Notice that the evaluation of G cannot bind its variables,
according to UNLP', therefore preserving the safeness condition
for negation as failure.
On a more pragmatic note, notice that "fail"
will backtrack into G until this fails completely - a waste of
effort. Therefore it seems a good idea to optimize this behavior,
by resorting to the Prolog cut and implementing A # <=C as:A
:- C, !, fail.
(But still enforcing the UNLP' restrictions on bindings,
taking C as the condition.)
This use of cut is certainly "safe": no
solutions are lost if a clause has a "fail" atom in
its body!
Stack space
Since soft_cut cuts only one choicepoint at a time,
and specially considering that it does it only on backtracking,
one may wonder if the local stack may grow much more than for
programs using cuts.
We conjecture that, overall, programs will become
more "deterministic", and that the cases where choicepoints
are created during evaluation of conditions will correspond to
those cases where the programmer actually wishes such choicepoints
to be kept…What may happen if an incorrect program computes ?
Advantages
We now sketch some of the advantages expected from
UNLP'.
No more jumping over goals on backtracking
Since programs will now be based mostly on soft_cut,
on backtracking all activated goals will fail completely. Determinism
is therefore enforced locally, instead of in the calling
context as some (bad!) Prolog programmers do. One soft_cut always
removes only one choicepoint.
Having no jumps over goal executions on backtracking,
at least for the bulk of the program, simplifies the problems
caused by side-effects that must be undone on backtracking. Typically,
on backtracking one wishes to call a goal undo_G for each side-effect
goal G that was executed previously. Since in UNLP' nearly all
goals fail completely, the undo_G calls can be simply done on
backtracking to g. The use of the Prolog cut being drastically
reduced, we conjecture that it is reasonable to treat it specifically,
typically via a trail-like mechanism to undo side-effects that
complements the standard scheme.
This should make life easier to implementors of (for
example): Delta-Prolog [Cunha 89], regarding cut failure over
synchronous events; Remote Predicate Calls [Calejo 89], regarding
failure over remote calls; sophisticated tracer debuggers [Calejo
Rosado 89], regarding update of proof tree display and undoing
of user side-effects; declarative graphics [Próspero Preston
?? …], regarding undoing of drawing actions.
Reduce "not not" use, thanks to soft_cut
UNLP programs
UNLP' suggests a challenge to UNLP programmers: if
UNLP programs are written declaratively, they'll need none or
little changing satisfactorily to run on UNLP'!
Converting Prolog programs
Prolog programs using a single cut per clause, not
within disjunctions, should be converted directly, by taking subgoals
to the left of the cut to be the "condition", and those
to the right to be the "then" branch. If cuts are used
"safely" [Lloyd 87], or are "green" [Sterling
Shapiro 86], than the resulting program will be UNLP'-correct
in many cases: those where the conditions will be mere tests.
There may be however safe uses of cut which will
not translate into UNLP'-correct programs. UNLP-correctness was
defined regarding (more or less!) local information to a predicate
definition. Non-local or semantic information which the Prolog
programmer uses may guarantee that a cut is safe, even if the
corresponding UNLP' program is not UNLP'-correct.
Of course, operational behaviour may be different,
affecting namely side-effects under conditions.Soundness (?), "more completeness", incompleteness awareness ?
Intelligent backtracking
Less dependencies than for Prolog cuts.
Debugging ?
The additional constraints allow more error conditions
to be detected automatically, relatively to Prolog.
Parallelism
The UNLP' restriction to goal variable bindings suggests
an opportunity for easier OR-parallelization of UNLP' programs:
all conditions of clauses in a predicate can be launched in parallel
without worrying about common variables, which are guaranteed
to be not bound. After computing a solution to a condition, all
processes corresponding to subsequent clause conditions can be
kild.
Proposal for work to be done
Short term
Add soft_cut to an existing Prolog compiler (YAP,
IM, SICSUS, QUINTUS…) ****NU-Prolog has it!
Adopt UNLP' at UNL
Explore static checking
Explore debugging of UNLP'
Long term
Reasonably efficient dynamic checking mechanism
Support some cases for the "greater" semantic
References
[Alegria 89] Personal communication.
[Calejo 89] Untiless UNLP meta-interpreters, Technical
Note, DI/FCT/UNL 1989
[Calejo 89] Remote goal solving through distributed
coroutining, Technical Note, DI/FCT/UNL 1989
[Calejo Rosado 89] Mister Tracer - A friendly Prolog
debugger, Technical Report, DI/FCT/UNL, forthcoming
[Cunha 89] PhD thesis
[Hermenegildo 89] "High Performance Prolog Implementation:
the WAM and beyond", tutorial, ICLP'89
[Lloyd 87] "Foundations of Logic Programming",
2nd edition, Springer Verlag 1987
[Naish 86] "…", Lee Naish, Procs.
of the 3rd Logic Programming Conference, Springer Verlag 1986
[Porto 83] Logical Action Systems, Procs. Workshop
on Logic Programming, Albufeira, Universidade Nova de Lisboa 1983
[Porto Pereira Trindade 87] UNL Prolog User's Guide
Manual, May 1987, DI/FCT/UNL
[Próspero 88 ?] Declarative Graphics…
??
[Sterling Shapiro 86] The Art of Prolog Programming,
MIT Press 1986
| 
Declarativa