🚀 go-pugleaf

|| / hpldola:comp.lang.prolog / djk@cs.mu.OZ.AU (David Keegel) / 12:48 am
|| Nov 23, 1989 /

| In article <11500019@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff)
| writes:

|| the danger of NON-TERMINATION is constantly rearing its ugly head.

|| I can either document these dangers in comments, mode declarations, or some
|| other "bag" on the side of the language, or I can rewrite my predicate to be
|| robust.  I, a self-styled purist, usually opt for the latter.

| Or you can use a co-routining system like NU-Prolog which can often
| delay evaluation of a predicate which would cause infinite loops.

I'm glad that you (and others) brought up NU-Prolog.  I am now more aware
that the *operational* semantics of Prolog should be kept distinct from its
*model-theoretic* semantics.  My goal of being able to generate all objects
in a domain upon backtracking is of no real value.  It leads to data
structures which are artifacts of the operational semantics of the
particular dialect of Prolog I'm using.  For example, my structure for
"sequences of natural numbers" was highly unnatural, but allowed all
sequences to be generated using standard, "eager" Prolog.  (Of course, I can
still do this with "standard" sequences if I first constrain the arithmetic
sum of all the elements in the sequence.)

This means that I can relax a little when I'm using Prolog.  Let's say I'm
writing a "file editor", and I have a function which applies an editing
command to a file:

    apply_command(Command, File0, File1).

    % File1 is the file resulting from the application of Command to the
    % file File0.

I don't have to worry too much about what happens when it's called with no
arguments bound.  I certainly don't need to enumerate all possible solutions
upon backtracking!  If Command and File1 are bound, but File0 is not, I
don't need to enumerate all possible solutions for File0.

Many relations implement functions which are not invertible in principle.
My reasoning about the termination properties of such relations is
intimately related to the *operational* semantics of the Prolog I'm using.
For example, in "eager" Prolog, I have no *general* way of preventing the
interpreter from "flying into the weeds" when File0 is unbound.  The Command
could implement an arbitrary function which cannot be inverted.

With NU-Prolog, I can control this behavior:  I can simply "block" on
Command and File0, but not on File1.  This gives me the ability to implement
robust "functions" when I have to, while retaining the power of logic
programming to implement more general "relations" when I can.

I still maintain that the danger of non-termination is higher in "eager"
Prolog than in any functional language, either eager or lazy.  In
particular, eager Prolog is more dangerous than eager ML.  In eager ML, you
know that arguments to functions will be ground terms, and you can reason
about termination accordingly.  In eager Prolog, you have no such knowledge,
and there are many nonterminating call modes that you cannot prevent.

Lazy Prolog is a "horse of a different color":  nontermination can often be
replaced by suspension.

Since I'm using eager Prolog, I'll just have to be careful, and document
things in comments.

||     object([]).
||     object([C|X]) :-
||         object(X),
||         construct(C, X).

| I don't understand why you don't have "construct(C, X), object(X)" as
| the body of the second clause, so you can use tail recursion. Never mind.

Because construct(C,X) is guaranteed to terminate a finite number of times
with C ground, but only if X is a ground term representing an object, and
the only way to guarantee that is to call object(X).  This is an artifact of
my desire to generate all possible objects upon backtracking, and my desire
to represent objects as ground terms.

Regarding my representation for natural numbers:

| (I thought s(s(....(s(0))...)) was the standard notation, but never mind.)

I figured that [] was a perfectly good niladic functor, so I might as well
use it to represent the natural number 0.  But that's kind of obscure, I'll
admit.  The fact that I'm using "0" right now to represent 0 is a good
argument against me!

|| In order to make things more efficient, I'll have to start
|| using more ad-hoc data structures.  For example, I could represent "sets" as
|| trees and get O(logN) access time.  But I'd have to give up my so-called
|| "constructive" ideal:  I doubt that it's possible to write omni-directional
|| predicates for manipulating trees, since they're doubly-recursive.

| I don't understand. What is the problem with double recursion? Why do
| you call trees "ad-hoc"?

Using trees obscures the specification.  I like to represents "sets of
objects" as lists, and just use the natural numbers 0, s(0), s(s(0)), etc.
to identify the objects.  It keeps things as simple as possible, but no
simpler.  Some of my algorithms are O(N^2) in the worst case, but the same
would go for trees unless I kept them balanced.  (Besides, I could translate
these specs into C using arrays and integer indices and get that blazing
speed I was talking about.)

Of course, I CAN write robust doubly-recursive predicates -- sort of.  For
example, the flatten/2 predicate below will work in all call modes, even
though it's a functional relation from T onto Xs.  I have to pass an extra
reference to Xs into an auxiliary predicate flatten/5 to give it something
to "chew on" before the left-recursive call.

    %----------------------------------------------------------------
    % flatten(T, Xs).
    %
    % T is a tree which is flattened to form the list Xs.
    %----------------------------------------------------------------
    flatten(T, Xs) :-
        flatten(T, Xs, [], Xs, []).

    flatten([], Xs, Xs, Ys, Ys).
    flatten(t(X,Ta,Tb), Xs, Xs0, [_|Ys], Ys0) :-
        flatten(Ta, Xs, [X|Xs1], Ys, Ys1),
        flatten(Tb, Xs1, Xs0, Ys1, Ys0).

However, the auxiliary predicate flatten/5 is "dangerous" in eager Prolog.
The query below succeeds with {T=[],Ys=[]}, and then fails to terminate upon
backtracking.

    flatten(T,[],[],Ys,[]).

I suppose I could document this in NU-Prolog with something like:

    ?- flatten(_,_,_,Ys,_) when Ys.

|| Besides, what is "first-order logic" other than Horn clauses?  (That's not
|| a rhetorical question.)

| First-order logic includes negation (you have heard of that, haven't
| you? :-), as well as implication and quantifiers.

I wanted to find out what O'Keefe was calling "first-order logic".  I
claimed that the "theory" behind Prolog was "pure Horn clauses"; he claimed
that it was "first-order logic", which includes negation.  In the literature
that I've seen, the semantics of Horn clause programs are defined model-
theoretically, but the semantics of negation are defined operationally (cit.
Chapter 5 of "The Art of Prolog").

A perverse reader might have surmised that my question was "yet another
example of the shocking absence of logic from our undergrad curricula".
You, in contrast, used a smiley face (:-).

Negation worries me.  A language feature should either be essential for
computation, or defined in terms of something that is.  Negation is NOT
essential for computation, so I HOPE that it can be defined in terms of pure
Horn clauses, which are.  Is there an effective procedure for removing
negation from a first-order logic program, resulting in a pure Horn clause
program?  I wouldn't necessarily USE the procedure -- I just want to know if
it exists.  If not, then something stinks.

This is one thing that I like about functional languages like ML and
Miranda:  everything in the language is just syntactic sugar for pure
combinatorial lambda expressions (K's and S's).

I'll continue to use the eager Prolog that's available to me.  I need to
find out about NU-Prolog, even if I don't use it.  At least it might give me
a "meta-language" for documenting (and thinking about) the termination
properties of my predicates.


Patrick Chkoreff   719-590-5983
{hpfcla,hplabs}!hpldola!patch


P.S.

/jha@lfcs.ed.ac.uk Jamie Andrews at Laboratory for the Foundations of
/Computer Science writes:
| My apologies if any of the flaming above caused serious
| offense.  :-)

None taken, but who pissed in your Corn Flakes?