PROLOG-REQUEST@SU-SCORE.ARPA (The Moderator) (08/24/85)
PROLOG Digest Monday, 26 Aug 1985 Volume 3 : Issue 37
Today's Topics:
Query - Simulation,
Programming - Building Large Systems,
LP Philosophy - Hewitts Challenge,
Implementation - Performance,
LP Library - Fix & Public Domain
----------------------------------------------------------------------
Date: Mon 12 Aug 85 20:11:56-PDT
From: Larry Widman <WIDMAN@SUMEX-AIM.ARPA>
Subject: Simulation
I am interested in semi-quantitative simulation as an
approach to generating scenarios of causal networks
which include feed-back loops. The scenarios could
then undergo feature extraction to permit temporal
reasoning and learning-from-experience by pattern
matching of specific scenarios with a library of
ideal scenarios ("compiled knowledge") and of
previously seen cases ("experience").
I have implemented such a program in MACLISP for use in
the medical domain. I presented it at the latest meeting
of the Artificial Intelligence in Medicine meeting in
Bethesda, in July. I should think that this approach
would be generally useful, and may well be under independent
investigation by others.
Therefore, I would like to read the logic programming
literature (the Digest being among the best, according
to my colleagues). If you think it is appropriate, you
could insert the above paragraphs into the Digest together
with a request for information from others with similar
interests.
I would of course be happy to summarize the responses for
the Digest.
Thank you for your help. -- Larry Widman
------------------------------
Date: Sun, 18 Aug 85 22:43:03 +0200
From: Anjo@seismo.CSS.GOV
Subject: Building Large Systems
We have had a similar problem with developing a window system
with a large number of utilities on top of Prolog. As the window
system should have a fast user interface (responding to mouse
clicks immediately), Prolog itself is not the most appropriate
language to use. Our solution is implement the user interface
and all the windowing stuff in C, along with text-editors, graphics
editors, the mouse-manager etc. (at the moment this is about 300+
pages of C source code). This package is called PCE. Obviously
the Prolog programmer wants full access to this package, he wants
to create windows, graphical representations of knowledge inside
his Prolog application and get mouse clicks if he needs them.
This calls for bi-directional interface between PCE and Prolog.
Our solution for this problem is to add a small number of
predicates to Prolog that implement object orientedness, and a
few functions that can asserted information available in PCE in
the Prolog data-base (total source code of these functions is
about 15 pages C).
The advantages of this approach (in our case) are that the
performance of the user interface doesn't depend on the performance
of the Prolog interpreter, so all I/O functions are as fast as C can
do it. The small interface assures that PCE can be modified without
also needing to change part in the interface. For example if we
decide to create another lay-out for a window only PCE needs to be
changed, while both the interface between Prolog and PCE, and the
Prolog applications remain unchanged.
Whether an approach like this is also feasible for your problem
depends, I think, on how well you succeed in keeping the interface
between Prolog and the "Data Base System (DBS)" simple. From a
software engineering point of view the saying "small is beautiful"
certainly applies here. I think that it is possible to build an
object oriented shell around a DBS, in that case the approach we
have used becomes possible. A dangerous approach is to add
predicates to Prolog for each operation you need, before long the
interface will be large and porting it to another implementation
of Prolog will for sure give problems. If we need to port PCE
Prolog to another implementation only 15 pages of C-code needs to
be rewritten, which is acceptable.
The Prolog implementation we use is C-Prolog 1.5 with some local
additions. If you would like to have more information or technical
details (the predicates used for instance) let me now it.
Greetings,
-- Anjo Anjewierden
------------------------------
Date: Mon, 19 Aug 1985 12:47 EDT
From: Hewitt@MIT-MC.ARPA
Subject: Prolog will fail as the foundation for AI
Date: Saturday, 17 August 1985 13:36-EDT
From: PEREIRA at SRI-AI.ARPA
Re: Prolog will fail as the foundation for AI
Carl Hewitt's message is based on several misconceptions:
1. (the least interesting one) All the so-called commercially
viable Prolog systems in Lisp are not really Prolog systems
written IN Lisp, but rather Prolog systems written FOR Lisp
machines. Or is it that a microcode sublanguage or Lisp machine
pointer-smashing operations are part of List as we know it?
Yes. They are DEFINITELY part of Common Lisp as we know it
being implementations of reading and writing operations on
record structures. Such implementation methods are NOT part
of Logic as a Programming language.
Without those machine-level operations, those Prolog systems
would run too slow and use too much memory to be useful for
serious Prolog programming. From the Prolog implementation
point of view, what is important about the Lisp machines is
not that they run Lisp, but that they can be microcoded and
have good support for tagged data types and stack operations.
It is important to many users that they can make use of ALL
the software available to the community and not just be limited
to the tiny amountin Prolog. Furthermore in the future good
software will be ported from stand alone Prolog systems to Prolog
implemented on Lisp. However to good Lisp software will not be
able to be ported to the stand alone Prolog systems.
2. If the decisions (actions) of a system are not determined
by its inputs, the system is nondeterministic. Nondeterminism
in a system can be either an artifact of our incomplete knowledge
(or lack of interest) of the detailed operation of the system;
or it can be ``real physical'' nondeterminism. It would take us
to far to discuss whether the second kind of nondeterminism is
``real'' or also an artifact. In any case, most uses of
nondeterminism, say in models of concurrency, are of the first
kind, and can be expressed appropriately in various temporal
dynamic logics. Admittedly, these are not Prolog, but then
Common Lisp is not Lisp 1.5! (Prolog is 13 years old, Lisp 25).
Yes indeed there is a large problem here that poses fundamental
problems for using Logic as a Programming language to make
decisions in Open Systems.
3. The first logic course dictum ``from a contradiction one
can conclude anything'' is getting in the way. Notice that
the dictum says ``can'', not ``must''. There is an enormous
difference between things that are in principle true and
things that an agent knows to be true in a way that can affect
its action. An agent might know ``p'' and ``not p'', but it
might well never come to infer the dreaded totally unrelated
``q'' which IN PRINCIPLE follows from the contradiction. This
inference might not happen either because of inference control
mechanisms of the agent (eg. it uses the set-of-support strategy)
or because the agent's logic is just TOO WEAK to conclude
anything from a contradiction (vide Hector Levesque's work in
the proceedings of the last AAAI). In any case, Horn clauses
(the basis of Prolog) are too weak to represent contradictions
... :-)
I claim that in practice the contradictions lie close to the
surface and occur in any nontrivial application. Thus the
contradictions pose fundamental problems for using Logic as
a Programming Language.
4. The question of whether ``taking action'' fits in a logic
paradigm tends to be answered negatively after an hour's worth
of consideration. If you persist for several years, though,
this question becomes a source of insight on the relations
between knowledge, state and action that is not available to
those who started by dismissing the question after that initial
hour. There is just too much work on logics of knowledge and
action in AI and computer science for me to try to discuss it
here. Some of this work has been applied to logic programming,
either in the form of new logic programming languages based on
temporal or dynamic logics or in representations of temporal
reasoning and decision in, say, Prolog.
I have been thinking about the problem for many years having
designed Micro-Planner, the first "procedural embedding of
logic" programming language in 1967. I claim that the problem
of taking action poses fundamental problems for using Logic as
a Programming language.
5. It is curious to see someone by implication defend Lisp as a
language for expressing the taking of action!
I claim that current Lisp systems are better than current Prolog
systems for taking action because the only ways to take action in
current Prolog systems are kludges.
We know by now that the most difficult issue in ``reactive
systems'' is not EXPRESSING action, but rather keeping it under
control to prevent unwanted interactions. In this area, less
is REALLY more, and highly complex languages like Lisp are
just not suitable for the formal reasoning about programs
that is needed to help us believe our programs do what we
intend. To those who say ``...but we can keep to a carefully
constrained subset of Lisp, use only message passing for
interactions,...'' I will answer that the history of all large
Lisp programs I know (and I think that is a representative sample)
is littered with the brutalized corpses of constrained
programming styles. Anyone who has looked at the current
flavor mechanism in Zetalisp and its use in the window system
will know what I mean...
5. Underlying Carl Hewitt's misconceptions is the old chestnut
``logic is static, systems are dynamic''.
Note that the above quotation is NOT anything that I said.
Any language, be it first-order logic or Lisp, is static;
it is its USE which is dynamic (changes the state of
communicating agents). A good analogy here is the use of
differential equations to model dynamic systems in classical
mechanics. The differential equations themselves do not say
directly what happens when (they are ``static'' in Hewitt's
jargon).
I do not deny that dynamic systems can be DESCRIBED using
logic only that they can be CONTROLLED.
It is their SOLUTIONS that tell us the sequence of events.
Even the solutions are given as static objects (functions
from an open interval of the reals to some space). Does
anyone worry that such equations do not ``really'' describe
the dynamic behavior of a system? Is it not possible to
combine such ``static'' entities with an incremental
solution procedure to build systems that actually control
their (classical mechanical) environment?
I do not believe that the control system can be implemented
using Logic as a Programming language
------------------------------
Date: Tue, 20 Aug 85 11:20:47 PDT
From: Rick McGeer mcgeer%ucbkim@Berkeley
Subject: Prolog In Lisp...
[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.
Wrong. I spent the better part of last year attempting to hack
up a decent Prolog in Lisp: the general idea was to use the
Prolog implementation for the top levels of the program, and a
Flavors-like "Object Engine" for low-level data structure hacking:
there were hooks in the logic engine to manipulate data structures
by calling the object-oriented stuff, and the trail was modified
to permit destructive assignment.
To make a long story short, the project failed because I couldn't
get decent performance out of the logic engine. So I threw out all
the data structures stuff and the Object Engine, and concentrated
on squeezing Prolog performance any way I could.
The result, after months of effort, traces, special purpose hacks
for fast unification of special cases, and so forth? 100 LIPS on
the concat loop on a 4MB Vax 11/780 running 4.2BSD. The
implementation was in Franz, Opus 38.91.
Why? Franz is simply too slow. I tried the concat loop, in
interpreted Franz:
(defun concat(l1 l2)
(cond ((null l1) l2)
(t (cons (car l1)
(concat (cdr l1)
l2)))))
and got these results:
Iterations Seconds Lips Equivalent
------------------------------------------------
100 .166 600
250 .3 833.333...
350 .417 840
400 Died N/A
I then tried running the same lists through Franz' native, tail
recursion optimized append function, and got:
Iterations Seconds Lips Equivalent
-----------------------------------------------
100 .03333 3000
250 .06666 3750
350 .1 3500
500 .13333 3750
1000 .26666 3750
Or, in short, compiled Franz runs at about 2.5 times the speed
of interpreted CProlog, and interpreted Franz runs at about half
the speed of interpreted CProlog.
Anyway, these figures were enough to convince me that Prolog in
Lisp wasn't going to be competitive with native-coded versions
(Cprolog and the compilers) for a long time, and I gave up. And
before you mention Lambda's Prolog to me, microcode support is
hardly a Prolog coded entirely in Lisp. Given microcode support
on the PLM, I'm sure that a viable Lisp-in-Prolog could be built.
-- Rick
------------------------------
Date: Tue, 20 Aug 1985 19:04 EDT
From: HEWITT@MIT-XX.ARPA
Subject: Prolog on Lisp vs. Lisp on Prolog
In the exhibitors hall at the IJCAI in Los Angeles, you
can find several commercially viable Prologs on top of
Lisp and Lisp Machines but no commercially viable Common
Lisp on top of Prolog.
Does anyone believe that it will EVER be possible to build
a commercially viable Common Lisp on Prolog?
-- Carl
------------------------------
Date: Tue, 20 Aug 85 16:58:10 PDT
From: Rick McGeer mcgeer%ucbkim@Berkeley
Subject: Prolog on Lisp vs. Lisp on Prolog
I'd be interested to see some figures on the performances
of these Prologs. Last year, various people told me that
any Prolog that didn't perform to the level of Warren's
compiled DEC-10 Prolog (which is to say, 20-30KLIPS)
wouldn't be commercially viable: on a VAX, (other things
being equal) such a Prolog should obtain about 5 KLips.
Now, it's clear that a Prolog In Lisp can't possibly do
better than the Lisp interpreter. Since even compiled Franz
can't hit 5 KLips, it is clear that no Prolog-In-Franz will
be commercially viable. Now, it's possible that dedicated
Lisp machines such as the 3600 or the Lambda can run a variant
of Lisp fast enough that Prolog can run in the commercially
viable range. However, if you're going to make that argument,
then the question you should be posing is whether dedicated
Prolog machines can run Lisp fast. And the answer is, sure
it can: a 200+ KLIP processor can run almost anything fast.
-- Rick.
------------------------------
Date: Wed, 21 Aug 1985 17:53 EDT
From: HEWITT@MIT-XX.ARPA
Subject: Prolog on Lisp vs. Lisp on Prolog
Why should a Prolog on Lisp be limited by the speed of
interpreted Lisp? I would imagine that the limitation
on speed would be that of highly optimized compiled Lisp.
-- Carl
P.S. What is your definition of a KLIP? For what purposes
do you think that KLIPs is a useful measure of performance?
------------------------------
Date: Wed, 21 Aug 85 15:19:58 PDT
From: Rick McGeer mcgeer%ucbkim@Berkeley
Subject: Prolog on Lisp vs. Lisp on Prolog
[Hewitt]:
Why should a Prolog on Lisp be limited by the speed of
interpreted Lisp? I would imagine that the limitation
on speed would be that of highly optimized compiled Lisp.
Well, I'd like to be wrong. If I could think of a way to
compile Prologcode into Lisp, then I'd agree. Unhappily,
I can't. The real trouble is maintaining the state of the
stack.
[Hewitt]:
P.S. What is your definition of a KLIP? For what purposes
do you think that KLIPs is a useful measure of performance?
A KLIP is 1000 Logical Inferences Per Second: I suppose that
would best be defined as succesful unifications, or function
calls. If you are going to argue that this is at best a
flawed measure of performance (since not all clauses are created
equal), then of course I'd agree. Performance studies here at
Berkeley have shown that it's easy to write the same program
two different ways, one of which runs faster and the other at a
higher LIPS rate. Still, a LIP is a handy catchall, much as a
MIP or a FLOP is...
-- Rick
[ Yawn. This definition is old, more or less resolved for
flap, peruse Volume 1 of the Archive -ed ]
------------------------------
Date: Wed, 21 Aug 1985 18:42 EDT
From: Hewitt@MIT-MC.ARPA
Subject: Prolog on Lisp vs. Lisp on Prolog
How do you measure the speed in KLIPS in practice. Do
you just measure the speed of APPEND in Prolog?
--Carl
------------------------------
Date: Wed, 21 Aug 85 18:27:08 PDT
From: Rick McGeer mcgeer%ucbkim@Berkeley
Subject: Prolog on Lisp vs. Lisp on Prolog
That is the way that I do it. Basically, I just
calculate the count of the call tree (not counting
failed unifications). Others may have other ideas.
Of course, you use other benchmarks. concat (or
append, if you prefer) tends to give you a pretty
optimistic answer.
BTW, a word about Common Prolog. It is fairly clear
that Prolog will need destructive assignment before
it becomes commercially viable: it turns out that the
major problem with destructive assignment (undoing the
assignments upon backtrack) is not all that hard to
solve. Once that happens, I imagine that you'll see a
large number of powerful, commercial Prolog systems.
-- Rick
------------------------------
Date: Thu, 22 Aug 85 12:55:46 pdt
From: Allen VanGelder <avg@diablo>
Subject: Re: minor fix for library
To users of my ranpkg in the Prolog library at
SCORE, if any: I replaced the expression
\(1 << (Wsize - 1))
by the more precise version,
\(\(0) << (Wsize - 1))
This has no effect using the current DEC-20 Prolog,
but makes the program less implementation-dependent.
Unfortunately my Cprolog converts large integers to
floating point without being asked, so extensive changes
were necessary to get around that "feature" and these
changes are not in the library.
------------------------------
Date: Mon, 5 Aug 85 10:09:19 pdt
From: Peter Ludemann <ludemann%ubc.csnet@csnet-relay>
Subject: Public domain Prolog, Hope
The August 1985 issue of BYTE magazine has a number of
articles on Declarative Langauges (Prolog, Hope, FP).
Public domain versions of Prolog (from Automata Design
Associates) and Hope (from Imperial college) for MS-DOS
machines are apparently available from BYTEnet at (617)
861-9774. Would some kind soul who lives in that area
please post these to this Digest? Phone lines here are
bad just going across the city; going across the
continent would be a nightmare.
-- Peter Ludemann
------------------------------
End of PROLOG Digest
********************