Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!ucsd!helios.ee.lbl.gov!pasteur!ucbvax!hplabs!hpfcso!hpldola!patch
From: patch@hpldola.HP.COM (Pat Chkoreff)
Newsgroups: comp.lang.prolog
Subject: Re: Fun. vs. Logic
Message-ID: <11500019@hpldola.HP.COM>
Date: 22 Nov 89 07:27:54 GMT
References: <11500018@hpldola.HP.COM>
Organization: HP Elec. Design Div. -ColoSpgs
Lines: 330

>> patch@hpldola.HP.COM (Pat Chkoreff) writes:
> ok@mudla.cs.mu.OZ.AU (Richard O'Keefe) writes:

>> Most Prolog predicates implement functions, so why not be honest and just
>> use a functional language?

> A function is a relation, so what's dishonest about using a relation?
> Don't laugh: but one of the things I like about Prolog is how easy it
> is to have a procedure return more than one value without having to
> make a special data structure to hold the values and without having
> to use special syntax.

Admittedly, things like divide(X,Y,Q,R) are nice, and it's nice to just use
append/3 instead of ldiff, append, and all those "functional" variants of
the same thing.  Absolutely.  But here's what ticks me off about Prolog:
the danger of NON-TERMINATION is constantly rearing its ugly head.  I write
a predicate, and then I immediately see how it is riddled with dangers when
I call it in certain ways.  I'm not even talking about dangers due to the
lack of the occurs check:  there's not a thing I can do about those.

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.

> So use functional syntax in your Prolog programs.  No-one's stopping you.
> I would point out, though, that I have _often_ found that the discipline
> of taking something that I initially thought of as a function, trying to
> express it in logic, and then asking "is it possible in principle to use
> this more than one way around" has led me to a simpler and more general
> interface.

Exactly.  That's what I do.  And I end up with omni-directional predicates.
But in order to do that, I have to come up with some really strange
representations for objects.  I suspect that these representations have a
lot in common with what is known as "constructive mathematics".  To build an
object, you start with [].  Given any object, there are a FINITE number of
constructors you can apply to create another object.  My domain predicates
for these objects always take the form:

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

The construct/2 predicate always returns a ground term for C.  Furthermore,
if X is a ground term representing an object, then C will be a ground term
representing a constructor applied to that object, and there are a FINITE
number of solutions for C.

What does all of this mean?  It means that if I invoke the query:

    object(X), write(X), nl, fail.

then the interpreter will systematically generate all possible objects in
the domain.  Of course, the objects must be recursively enumerable, but that
goes for anything you can represent in a computer.

>> It is very difficult, if not impossible, to
>> write Prolog relations which work robustly in "all directions".

> The simple reason for this is that many predicates have infinitely many
> solutions in some directions.  But I fail to see why the fact that a
> predicate can't be used ALL ways round is a reason for only letting me
> use it ONE way round.  Why not let me use it in all the modes where it
> does work?

But how do you determine the modes in which it works, how do you document
them in the language, and what does it mean to the compiler?  What would you
end up with?  A sort of hybrid functional/logic language?  GREAT!  I'd fill
out a purchase request for that.

By the way, I'll bet that a lot of predicates which SEEM to have infinitely
many solutions in some directions can be recast so that they don't.  The
problem is:  it's a major pain in the ass.

Here's an example.  Let's write a predicate which defines "sequences of
natural numbers" in a straightforward way.

    sequence([]).
    sequence([N|Ns]) :-
        natural(N),
        sequence(Ns).

    natural([]).
    natural(s(N)) :-
        natural(N).

Now we write a predicate card(Ns,N), meaning that the cardinality (length)
of Ns is N:

    card([], []).
    card([_|Ns], s(N)) :-
        card(Ns, N).

Now we look for sequences of cardinality 2 (s(s([]))):

    sequence(Ns), card(Ns, s(s([]))).

We get one solution Ns=[[],[]], and on backtracking we fly off into the
weeds.  I know that I could fold card/2 back into sequence/1, but I could
replace card/2 with an arbitrarily complex condition which might be very
difficult to unfold.

So here's the bottom line.  In order to get REALLY robust predicates, it
boils down to the ability to do a robust generate-and-test:

    interesting_object(X) :-
        object(X),
        interesting(X).

This should iterate over all interesting objects, where the interesting/1
predicate is arbitrarily complex.  Of course, if there are no interesting
objects, then it will not terminate.  But that's life, and I can live with
that.

Let's apply this criterion to our example.  We must rewrite the domain
predicate sequence/1 to be a robust generator.  To do this, we must adopt a
purely "constructive" representation for sequences:

    sequence([]).
    sequence([C|Cs]) :-
        sequence(Cs),
        construct(C, Cs).

    construct([], _).
    construct(s(C), [C|Cs]) :-
        construct(C, Cs).

Now it's a little tricky to interpret these lists of constructors as
sequences of naturals, so I've provided a function interpret(Cs,Ns) which
maps a Cs-style sequence into the more familiar Ns-style sequence:

    interpret(Cs, Ns) :-
        sequence(Cs),
        gather(Cs, Ns).

    gather([], []).
    gather([C|Cs], [C|Ns]) :-
        toss(C, Cs, Cs0),
        gather(Cs0, Ns).

    toss([], L, L).
    toss(s(N), [_|L], L0) :-
        toss(N, L, L0).

If you invoke the query:

    ?- interpret(_, Ns), write(Ns), nl, fail.

then Prolog will begin enumerating all possible sequences of naturals, and
you'll see them in a familiar notation.

By the way, don't try to run the interpret/2 function backwards.  You'll get
the unique solution, but on backtracking it'll go into the weeds.  Oh well,
that's yet another nontermination quirk that I'll have to squash (if
possible).

Anyway, I've done these "constructive" representations for many kinds of
objects:

    -    natural numbers (trivial)

    -    rational numbers

    -    sequences of natural numbers

    -    partitioned sets

            This will iterate over all ways of partitioning N objects into N
            or fewer non-empty classes, for all N >= 0.

    -    directed acyclic graphs

            This will iterate over all possible DAGs, with any number of
            vertices and any number of edges between any two vertices.  I
            suspect that allowing cycles should be a fairly simple
            extension.

    -    entire block design hierarchies with connectivity

            A "design hierarchy" is used in computer-aided design.


As I said, this was a major pain in the ass.  But O'Keefe is right:  by
trying to make robust relations instead of just functions, I achieved some
strong insights.

The problem is:  I'm not sure that my data structures are practical.  In the
worst case, they're all O(N^2) in both time and space.  I could get rid of
the s/1 notation for numbers and save some space, but that's about all I can
do in Prolog.  However, it's interesting that all of these structures could
be implemented with arrays and integer indices in a language like C, and
they'd be really fast!  (But I'm not in a great hurry to code in C.)

>> In Prolog, there is a wide divergence between theory and practice

> The width of the difference is a good measure of the ability of the
> programmer.  Wide gap = bad programmer or bad implementation.

The problem is that I held onto the theory like a man possessed, and I might
have ended up with something totally impractical.  Perhaps I'm a bad
programmer.  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.

>> That allows me to do things
>> like manipulate graphs as full-fledged objects, rather than as data
>> scattered around in extensional relations.  I can do that in pure Prolog,
>> too, but it ain't easy.

> Damn right it's easy.  I've done it.

Yeah, but I'll bet your graphs weren't "constructive".  I'll bet you used
atoms as node identifiers, didn't you?  (:-)

> The theory is not "pure Horn clauses" but "first-order logic".

That's where we differ.  Notice that all my code consists of pure Horn
clauses.  I understand that I have to give up that ideal in order to do I/O
and machine arithmetic, but I stick to the ideal as long as possible.
Besides, what is "first-order logic" other than Horn clauses?  (That's not a
rhetorical question.)

> In NU Prolog, there are logical versions of not/1 (not/1 *is* the logical
> version, as in DEC-10 Prolog and Quintus Prolog; \+ /1 is the unsound one)
> and all-solutions predicates, and thanks to indexing, a competent programmer
> doesn't need many cuts at all.  And while NU Prolog is not the world's
> fastest Prolog system, it's not bad.

I'd like to see NU Prolog working on this database:

    person(pat).
    person(diana).

with this query:

    ?- not person(X).

I'm guessing that either X remains an unbound variable which is constrained
to not be a person, or the query freezes on X.  What DOES happen?

As far as "cuts" go, you certainly don't need them in functional languages:
they are replaced with "commitment".  Of course, you still have order
dependencies, where a clause is chosen only if its guard is true and the
disjunction of the preceding guards is false.  But "commitment" is
fundamentally syntactic sugar, whereas "cuts" are not.  You could replace
"cuts" with negated conjunctions, but how do you define negation?  In terms
of cuts, most likely.

>> Furthermore, functional programming languages are strongly typed and
>> higher-order, which cannot be said for Prolog.

> Functional languages do not have to be strongly typed.
> Prolog *can* be strongly typed.  My formal specification of Prolog is
> a strongly typed Prolog program.  (NU Prolog these days has two type
> checkers that I know of.  Lee Naish's one is really amazing.)

> Prolog-as-we-know-it is not higher order, but that doesn't stop me using
> maplist and such things in Prolog, and there is Lambda Prolog which is a
> higher-order logic-based language.

As I read about functional programming languages such as Miranda or ML, I am
impressed with their purity, coherence, simple model of execution, and
support for large-scale and higher-order programming.  Every program
corresponds to a lambda expression, and execution is essentially
beta-reduction.  Modules, concrete types, abstract types, and functional
data are a coherent part of the language.

Now pure Prolog is a slick little language, too.  But then you add cuts,
negation, and findall.  And then you add type checkers and mode
declarations.  And then you invent extended languages.  You stick all these
"bags" on the side of Prolog, and the result just doesn't cohere as well as
I'd like.

Let's say I want to write a Prolog program which maintains a dynamic
database of facts.  I can store the facts in the internal database and use
assert and retract.  But that's not clean.  So I decide to represent the
database as a data structure and filter a transaction stream through it.  I
write "relations" which edit the data structure, but they're not reversible,
and in general it is IMPOSSIBLE to make them so.  (Note well:  impossible.)
Certain query modes will be meaningless and probably nonterminating.

Since in general I cannot implement completely robust relations, then give
me a language that allows me to document functional dependencies and types,
and make them meaningful to the compiler.  That would be more "honest" than
a language which LOOKS relational but really isn't, and is fraught with
dangers if you think that it is.

> One thing which Prolog programmers ought to copy from functional programming
> is the determination to stick with the theory as long as possible:  it
> really is the case that clean Prolog code tends to be faster than hacky
> stuff.

I think that I might have stuck with the theory longer than possible (:-).

In my original posting, I mentioned that some functional languages have
destructive assignment.  In response:

>markv@phoenix.Princeton.EDU (Mark T Vandewettering) writes:
> AIIIGH!  The horror!  ASSIGNMENT?
>
> Destructive assigment is an atrocity, and totally against the spirit of
> functional programming, neatly messing up lots of nice properties.  I am
> for a language without the crutch of assignment.

I agree.  I am for a pure language without crutches.  What I failed to
emphasize was that with one exception, EVERY example in "Elements of
Functional Programming" was written in the PURE language.  Destructive
assignment was used in only one place, simply to demonstrate how lazy
evaluation could be implemented in an eager language.  In contrast, MOST
Prolog programs use "impure" constructs and are not purely "relational".  So
are we in the position that virtually EVERY functional program is purely
functional, but virtually NO Prolog programs are purely relational?

Although I may sound extremely hostile to Prolog, keep in mind that I have
learned things using Prolog that I probably wouldn't have learned using
Miranda.  And I'm not "sold" on functional programming:  it seems less
general than logic programming.  It is certainly the case that the class of
mathematical relations is a proper superset of the class of mathematical
functions.  But pure relations are so difficult to implement robustly, and
pure functions are so easy, that I wonder what is going on here.  Perhaps
relations are more general, but functions are more computationally "honest".

Or what?


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