PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (09/25/85)
PROLOG Digest Wednesday, 25 Sep 1985 Volume 3 : Issue 38
Today's Topics:
Query - Books-in-print database,
Challenge Problem - Ken Laws,
LP Philosophy - Hewitt's Challenge,
Programming - Building Large Systems,
Implementations - Cut Test & Destructive Assignment,
LP Library - Update
----------------------------------------------------------------------
Date: Mon, 9 Sep 85 10:42 PDT
From: RGARRETT%LAJ.SAINET.MFENET@LLL-MFE.ARPA
Subject: Books-in-print database
I assume you are familiar with "Books in Print" , the multi-volume
listing of most of the books currently in print in the USA. I
would like something similar but on magnetic media;i.e., mag tape
and hopefully cheap. The purpose of this is to serve as the
foundation for an expert system retrieval system to be written in
(what else) PROLOG. Since this is both an experimental system (how
many other kinds of expert systems are there?) and done as a
graduate student, I am only interested in public domain or very low
cost sources. I am already familiar with commercial systems such
as DIALOG and with IRList. I hope this answers your questions, but
if something is still unclear, just drop me a note.
-- Randy Garrett
------------------------------
Date: Thu, 29 Aug 85 10:39:26 pdt
From: Allen VanGelder <avg@diablo>
Subject: Ken Laws' challenge problem
The problem statement assumes some familiarity with image
processing jargon. I am guessing that he is talking about
a 2-dimensional array and that two elements are "connected"
if they are within 1 of each other on both indexes, i.e.,
diagonal adjacency as well as horizontal and vertical
adjacency is connected.
The advantage of a logic-based language, if any, is not to
remove ALL procedural responsibility from the programmer, but
to provide a way to write procedures that have a close enough
connection to the specifications that they can be informally
verified. For example, I can write
neighbor((i,j), (k,l)) :-
not ((i,j) = (k,l)),
adjacent(i, k),
adjacent(j, l).
adjacent(i, j) :-
(i = j; i is j+1; j is i+1).
Note that semi-colon is read "or" and ":-" is read "if" and
comma is read "and". This "procedure" can simply be read in
English as a specification of "neighbor", yet it is also the
Cprolog source code.
Arrays are certainly a problem in logic programming, and Ken's
problem is a good challenge. But he should not expect to see a
naive problem specification that runs as a Prolog program. He
IS entitled to ask for a logic program that is both efficient
and informally verifiable. I don't have that for him.
------------------------------
Date: 05 Sep 85 18:29:55 PDT (Thu)
From: Sanjai Narain <Narain@rand-unix.ARPA>
Subject: Response to Hewitt
>Prolog (like APL before it) will fail as the foundation for
>Artificial Intelligence because of competition with Lisp.
>There are commercially viable Prolog implementations written
>in Lisp but not conversely.
For the same reason, Lisp should have failed as a foundation for
computing because of competition with assembly language.
There are commercially viable implementations of Lisp in assembly
language but not conversely.
>LOGIC as a PROGRAMMING Language will fail as the foundation
>for AI because:
>1. Logical inference cannot be used to infer the decisions
> that need to be taken in open systems because the decisions
> are not determined by system inputs.
>>2. Logic does not cope well with the contradictory knowledge
>> bases inherent in open systems. It leaves out
>> counterarguments and debate.
>>3. Taking action does not fit within the logic paradigm.
1. Hewitt clearly states in his recent BYTE article that
traditionalnotions of computation as defined, for example,
by Turing machines or recursive functions cannot model the behavior
of open systems. Hence even Lisp is inadequate for such modeling
(by his reasoning).
2. The notion of contradiction (i.e. inconsistency) is well
understood in logic.
3. The statement is too vague for debate. What do the words
"action" and"fit" mean? Certainly, if action can be modeled
by an effective procedure, it can be modeled by logic, cf. 1.
-- Sanjai Narain
------------------------------
Date: Thu, 5-Sep-85 13:40:43 PDT
From: (Tom Khabaza) mcvax!ukc!warwick!cvaxa!tomk@Seismo
Subject: On Hewitt's "Prolog and logic programming will fail"
I have read with interest the discussion following Carl Hewitt's
"Prolog will fail as the foundation for AI and so will Logic
Programming". I particularly enjoyed Vijay Saraswat's reply, most
of which I agree with. However, I would like to add a few comments:
In some ways I was surprised by the original message; I should
have thoughtthat if AI has taught us anything, it is that to solve
a given problem, we need a good representation language. Why anyone
might think that logic is the BEST representation language for every
problem is beyond me. (No Kowalskiist flames please, I know the
arguments, and I don't regard the case as proven.)
On the other hand, we don't yet know what the limits of logic
programming are; researchers in the field are constantly coming up
with new techniques. There is convincing evidence that logic
programming is better than conventional programming for some kinds
of task, at least with regard to ease and clarity (though probably
not yet efficiency).
But I think the basis of the original comment goes deeper than the
virtues and vices of logic programming. As I understand it (and I
wasn't around at the time) some earlier AI programming languages,
such as perhaps micro-Planner and its successors, WERE expected to
become a "foundation" for AI. Perhaps this was because people still
had hopes for the notion of some "ultimate" representation language,
or family of languages.
AI is older and perhaps more cynical now; I don't think we expect
some single foundation to the field in the form of a representation
language. Logic programming may be very useful for some parts of
AI; for example some kinds of rule based systems, but I don't expect
it to be the best tool for all kinds of AI programming. In fact my
personal opinion is that logic programming will find its forte in
more conventional Computer Science, where formal specification is a
more practical proposition than in the relatively exploratory
activity of AI programming.
But I will say this in its favour: logic programming is IMPORTANT.
Logic programming is as different from conventional programming as
programming is from not programming at all. I have met people who
have given up on Prolog because it was difficult for them and they
(rightfully) considered themselves competent programmers - and so
thought it must be Prolog's fault! (I don't mean to imply that
anyone who has posted in this discussion is such a person.) But
logic programming is different in fundamental ways; it's worth
presevering to get to the bottom of it, and as logic programming
languages improve, it will become even more so.
So for all you computer people out there, USE Prolog, and study
how other people have used it. It really is worth it.
------------------------------
Date: Tue, 20 Aug 85 21:07:41 EDT
From: Stephen Wolff <steve@BRL.ARPA>
Subject: Another precinct heard from
"Cut test" results for University of York Portable
Prolog, V2.1:
Test
1 2 3 4 5 6
Y Y Y Y Y N
------------------------------
Date: Wed, 28 Aug 85 09:06:26 -0200
From: David McKelvie <mcvax!unido!ecrcvax!david@seismo.CSS.GOV>
Subject: User Interfaces - Building Large Systems
We, the ECRC Man-machine interaction group, have had similar
problems with the slowness of Prolog interpreters for handling
interactive graphics, and have come up with a similar solution.
We have split off the user interface part into a seperate
process (we are using UNIX) and communicate to Prolog via a
pipe, rather than a direct connection to the Prolog database
as you seem to have. However we are having problems in defining
what sort of interface there should be between the UI and Prolog.
Therefore, we would be rather interested in the technical details
of your interface, in particular the Prolog predicates you have
defined, and what you mean by 'object orientedness' ( a horrible
term for a good idea). Does this allow a more declarative than
imperative way of defining pictures from Prolog?
Thank you
-- David Mckelvie
(ECRC stands for European Computer-Industry Research Centre, a
centre funded by European computer companies, mainly doing work
on Logic programming and Knowledge bases. A sort of miniature
version of ICOT or MCC )
------------------------------
Date: Wed, 28 Aug 85 22:32:37 PDT
From: (Rick McGeer) mcgeer%ucbkim@Berkeley
Subject: Destructive assignment
Dedicated hardware isn't magic, you know. You still fill up
space with garbage, and there is no particular reason to believe
that you're going to be able to predict or control where you leave
it. Also keep in mind that if you have a paged virtual memory
system, you experience an enormous degree of internal
fragmentation if your wastage is large and is spread evenly over
more or less half your pages. That's a recipe for thrashing....
The other, major problem with no destructive assignment is time.
If you want to change a small field buried deep inside a large
record, you have to copy the entire record. On interpreted systems
this is not so bad since structure is shared. On compiled systems,
such as Warren & Tick and Berkeley PLM, it's an absolute disaster
because such machines copy rather than share structures. In that
sense compiled code on special-purpose h'ware performs more
poorly than interpreted code on a gp machine.
Some computations are history-sensitive, and that's all there is
to it. Either your programming language recognizes these realities
or it doesn't. If it does, it's useable; if it doesn't, it becomes
a delight for mathematicians and unused by everyone else. Lisp
implementers swallowed hard, gave up purity, and put in setq and
rplacd. Lisp is used and useable. FP and Lucid implementers,
among others, stuck by no-assignment semantics and washed up on
the ash-heap of programming languages. People who implement
Prolog are faced with the same choice, and will face the same
results.
-- Rick
------------------------------
Date: Fri, 30 Aug 85 13:24:56 PDT
From: (Rick McGeer) mcgeer%ucbkim@Berkeley
Subject: Destructive assignment
Here's a good example of when you really need destructive
assignment in Prolog. I'm currently writing an IC layout
expert in Prolog. At one point in the program, nets are
assigned to rows. When this is done, the row's freelist
and wirelist is updated, and so, of course, a new row is
generated.
Now, the difficulty is that the net structure includes the
row that the net runs on. Unfortunately, this row may be
regenerated later with a different freelist. When this happens,
the row pointed to by the net structure disappears from the
list of rows in the grid, so that later processing reports
that the row doesn't exist.
The solution is to keep an (atomic) ID field in each row and
index through that. This both complicates the code and
increases the running time, and obscures what's really going
on.
I might point out that other researchers in this area started
out with Prolog and then went to other languages (eg, C), largely
for these sorts of reasons. Dwight Hill of BTL, who gave a paper
at ICCD '84 on "The Silicon Converter: A Case Study in Uses For
Prolog" has now gone over to C for IC placement and routing.
-- Rick
------------------------------
Date: Fri, 13 Sep 85 01:09:57 edt
From: Tom Blenko <blenko@rochester.arpa>
Subject: Destructive assignment
I agree with your points about the time/memory costs
and difficulties associated with either copying or sharing
data structures.
First point: if you add destructive assignment to PROLOG,
it isn't (even nearly) PROLOG anymore.
Second point: the issues you raise are more clearly critical
for functional languages. I don't agree that FP and LUCID
are washed up on the ash-heap of programming languages: FP
was basically a model for a functional language, not a proposal
for an implementable, production-oriented language. There are
people working quite seriously on the implementation of functional
languages (I am less familiar with serious work on implementation
of declarative languages). I agree that there are as yet no
visible successes, but it is certainly too soon for the jury to
come back in.
We can look at how the LISP machine people addressed the problem
in their design: large VM, large physical memory, cacheing of
everything they could think of, and more recently (not yet released)
garbage collection out of the cache. I don't know the details of
the scheme, but I think it may have been published, and they are
claiming improvement by a factor of two in performance as a result.
I know also of a major computer manufacturer which is implementing
a chip based on SASL. They claim on-the-fly garbage collection,
although emergency (out-of-space) collection is provided.
One performance benefit of functional (and perhaps logic
programming) languages may come in their parallel execution --
specifically that this may be easier to accomplish than for
languages with destructive assignment. I have looked at this
for Concurrent Prolog, and the
write-once property of variables plays a very important role in
reducing the complexity of inter-process communication.
In sum, I agree that there are problems, and I agree that the
solutions are not in hand, but I think it is hasty to conclude
that solutions are not possible, especially since we are really
in the infancy of architectures designed with such languages in
mind.
-- Tom
------------------------------
Date: Sun, 11-Aug-85 19:32:53 PDT
From: ihnp4!houxm!mhuxt!mhuxr!ulysses!burl!clyde!watmath!utzoo
Subject: Supplement to C-Prolog manual, Grammars, Exanmples, etc.
The User's Manual for DEC10 Prolog (circa 1978) had several useful
sections on definite-clause grammars, grammar rules for "Edinburgh"
syntax, example programs, and (early) Prolog references. None of this
information was in the C-Prolog manual distributed with C-Prolog 1.5,
so before our beloved (:-)) TOPS-10 machine vanished into obliv
-ion, I converted these sections into "troff -ms" format to serve as
an appendix to the C-Prolog manual which we distribute to students in
a LP course here. There is no copyright on this material, as far as I
can tell, so I hope F. Pereira & Co. won't mind. I'm postingthe
excerpts to the net, at the suggestion of a colleague. I wouldn't
mind hearing from anyone who found it useful (or who objects to long
articles containing material of ancient vintage); it's hard for me to
gauge whether or not purely pedagogical material such as this should
be circulated on the net.
[ This is available from the SCORE: <Prolog> libray as:
CProlog_Supplementary_Manual.Txt and can be netted over,
if you can't access SCORE: send a request to Prolog-Request -ed ]
------------------------------
End of PROLOG Digest
********************