Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!ucsd!sdcsvax!ucsdhub!hp-sdd!hplabs!hpfcdc!hpldola!patch
From: patch@hpldola.HP.COM (Pat Chkoreff)
Newsgroups: comp.lang.prolog
Subject: Re: Higher Order Extensions
Message-ID: <11500015@hpldola.HP.COM>
Date: 21 Apr 89 22:32:59 GMT
References: <11500013@hpldola.HP.COM>
Organization: HP Elec. Design Div. -ColoSpgs
Lines: 90

/ hpldola:comp.lang.prolog / jah@lfcs.ed.ac.uk (James Harland) /  6:53 am  Apr 19, 1989 /

> It is a little hard for me to understand what you are getting at here.
> ...
> However, the result you quote in the last sentence
> above is not really relevant to this discussion, as whilst pure Prolog is
> equivalent to (your favourite variation of) Turing machines, there is the
> question of convenience. Turing machines are adequate for computation, but
> does anyone seriously wish to program such beasts? A less extreme comment
> may be made about pure Prolog; it is computationally sufficient in the
> sense you mentioned above, but is it expressive enough for *convenient*
> programming? This seems to be the question that you are addressing.

I thank Richard O'Keefe and James Harland for their responses.  Allow me
to clearly state the intent of my posting, which I should have done in
the first place.

I have had a recent experience (epiphany?)  that makes me wary of the
`convenience' of using extensions outside of pure first-order logic,
including findall/3, !/0, and \+/1.  I do not claim that they are
unnecessary for building practical systems, and I do not claim that
there is a moral imperative not to use or implement them.  I claim that
their convenience may lull you into using them even though a perfectly
logical solution could be found if you tried.

My experience is with the manipulation of weighted attributed directed
acyclic graphs.  I started by encoding the weights, attributes, and
edges as relations (i.e., into the program).  To verify that the graph
was acyclic, I had to use extensions.  To do attribute synthesis, I had
to use extensions.  And I used 'em all:  findall, !, \+ -- the works.
Given my data representation, I had no choice.  I found myself having to
repeatedly write essentially the same 26 lines of cut- and findall-
laden code for the various tasks.  No really viable leap of abstraction
was possible.  I tried some ideas similar to the one O'Keefe suggested,
but they didn't go far enough.

Finally, I committed myself to the task of representing arbitrary DAGs
as terms in pure first-order logic.  I mean _pure_:  no arbitrary atomic
node identifiers, no extralogical extensions, no arg/3 or functor/3, not
even any machine arithmetic.  I wanted those things right out there in
the Herbrand universe where I could denote 'em.

I succeeded.  Now, I don't have to _check_ that a graph is acyclic:
there is no way to even _express_ a graph with cycles.  I wrote 8
(eight) lines of pure, general-purpose code that related together a
graph, edge weights, input attributes, and output attributes.  It's an
excellent generator:  if you wait long enough, you'll see any solution
that exists.  In retrospect, my solution is trivial, and that's why I
like it.

To deal with the inefficiencies of computing with the natural numbers []
(zero) and s(N) (N+1), I build natural expressions, postponing their
evaluation as long as I desire.  This also preserves the generation and
termination characteristics of the predicate, preventing it from
mindlessly generating ever-increasing natural numbers or getting lost
searching for things that don't exist.

If I want to convert an expression to a machine integer, I have a
predicate that will do so (using machine arithmetic, of course).  So
even though I have attributes with values such as 144140, I never need
to build a term of that depth.

Here's the scary thing.  This version is much more efficient than the
old one.  I haven't even counted the efficiency gained by simply reading
the data instead of asserting it.

I could easily fold the evaluation back into the attribute synthesis,
making it work directly with machine integers and floats, but I don't
really need to.  In any case, at least I have a working specification.
Those 26-line monsters were not only illogical, they didn't even have
the decency to fit on a single screen!

Thus, my limited experience suggests that although extralogical
extensions may seem convenient, a purely logical solution is out there
waiting for you.  It may be coy and elusive as hell, but its rewards may
far exceed the cost of the search.  Then again, maybe not.

I would certainly desire a language based on a higher-order logic.  That
would spare me from having to rely on ad hoc (albeit useful) language
extensions when things get really tough.  I want a language that allows
me to express what I want cleanly and logically, and when that's
impractical, I'd like a good C interface.

I am obviously somewhat religious on this point, and would thoroughly
appreciate a good bash from an wise iconoclast.  I'm venturing into a
new area of my project now, where my faith will be tested in a much
hotter fire.


- Patrick Chkoreff                 "Ada:  it's not just a language ...."