PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (09/29/85)
PROLOG Digest Monday, 30 Sep 1985 Volume 3 : Issue 41
Today's Topics:
Query - Prolog for Apple IIe,
Challenge - Ken Law's,
LP Philosophy - Hewitt's Challenge,
Implementation - DCG's & Destructive Assignment
----------------------------------------------------------------------
Date: Wed, 25-Sep-85 14:38:38 PDT
From: (Craig D. Singer) mcnc!duke!cds@UCB-Vax.ARPA
Subject: Prolog for Apple IIe
Does anybody know where we might purchase a non-copy-protected
version of Prolog for the Apple IIe? This software is strictly
for educational use, and we have about three or four Apples we'd
like to be able to run it on simultaneously; hence, the need for
a copyable program. One or two of the Apples are enhanced and
one or two of them are not, but that is not a major concern.
We simply need software which our AI grads can use without having
to handle the disk with extreme delicacy. Alternatively, we would
consider purchasing (or, ahem, graciously accepting) the printed
or downloaded source. If you can help, please send mail or post
something here...we read this newsgroup daily.
Thank you now for good deeds later!
-- Craig Singer
------------------------------
Date: Fri 27 Sep 85 16:14:09-PDT
From: Ken Laws <Laws@SRI-AI.ARPA>
Subject: Connected-Component Extraction
My thanks [to Allen VanGelder] for considering the connected
-component extraction problem. After sending it off to Phil-Sci,
I realized thatI was really asking for an automated programming
solution rather than a logic programming solution -- and I don't
expect anyone to come up with one. The question remains, though,
whether expressing a problem in a logic formalism will help the
programmer develop an algorithmic solution. I'm sure the answer
depends on the problem, the logic formalism, and the programmer.
The problem statement was a little imprecise. I did indeed have a
2-dimensional array in mind, although I believe that any algorithm
would be essentially the same for higher dimensionalities. I also
had just rectilinear neighbors in mind, although permitting diagonal
neighbors makes just as good a problem. (There is a quirk in the
computational geometry, though; allowing diagonal connectedness
permits connected components that intersect each other. This
plays havoc with containment relationships. Some pattern
recognition systems use diagonal connectedness for foreground
objects and rectilinear connectedness for the background, but
that won't work for other than binary arrays.)
Shortly after submitting the problem, I ran across an algorithm
for solving it (in the binary case) using a pyramid of
interconnected processors. The algorithm was so clever that I
can't remember it now. Maybe we do need automated programming
systems to derive optimal algorithms for any hardware or
circumstance, but some of the procedural solutions people have
invented (often for ill-defined problems) are awe-inspiring.
-- Ken Laws
------------------------------
Date: Thu, 26 Sep 85 10:29 EDT
From: Tim Finin <Tim%upenn.csnet@CSNET-RELAY.ARPA>
Subject: Lisp and Prolog
PROLOG/LISP = LISP/C
I'd like to amplify a point of view Clocksin put forth in V3
#39 in the great LISP vs. PROLOG debate. Prolog (and Logic
Programming in general) and Lisp are both tools which are suited
for different tasks. Luckily, none of us is being forced to use
one to the exclusion of the other.
I've had to give more than my share of introductory AI talks over
the years. When the discussion gets around to Lisp I usually point
out that Lisp is especially attractive for experimental programming
situations, i.e. where you know what you want to accomplish but do
not yet have all of the details as to algorithms, data structures,
etc. worked out. Once you've worked out the last detail, you can
re-implement your system in C, if you like, and gain the benefits
of a faster and smaller system.
Along these lines, I think that the slogan "Prolog is to Lisp as
Lisp is to C" is not too inaccurate. I think that Prolog is even
better suited to initial, experimental and exploratory attempts to
attack a problem computationally. I find that it is a very
convienent paradigm in which to get started. Once I have a better
idea of how to reprent a problem and how to manipulate the
representation, I can re-implement it in Lisp and gain a faster
more steamlined system.
-- Tim
------------------------------
Date: Thu 26 Sep 85 15:45:15-PDT
From: Fernando Pereira <PEREIRA%sri-candide@sri-marvin>
Subject: DCGs and parsing strategy
First, let's get rid of one misconception about DCGs. DCGs
are not ``top-down'' any more than, say, context-free grammars.
I have top-down, bottom-up, left-corner, Earley, and various
chart-parsers for DCGs, all implemented in Prolog.
Now for the minimal bottom-up (actually, left-corner) DCG parser.
The parser is itself a DCG (a DCG metainterpreter, if you wish)
that takes rules given by the binary predicate ==>. To parse a
string S as having category C, call
?- down(C,S,[]).
Here is the code:
down(Phrase) --> leaf(SubPhrase), lc(SubPhrase,Phrase).
leaf([Word]) --> [Word].
leaf(Phrase) --> { Phrase ==> [] }.
terminals([]) --> [].
terminals([Word|Words]) --> [Word], terminals(Words).
lc(Phrase,Phrase) --> [].
lc(SubPhrase,SuperPhrase) -->
{ Phrase ==> [SubPhrase|Rest] },
right(Rest),
lc(Phrase,SuperPhrase).
right([]) --> [].
right([Phrase|Phrases]) -->
down(Phrase),
right(Phrases).
Note that the sequence of symbols to the right of the arrow is
written as a list (rather than as a `,'-separated sequence) in
the object grammar. A few modifications are needed to handle
{...} conditions and terminal sequences [...]. It is possible
to make the code much more efficient by partial evaluation
with the object grammar and other compile-time optimizations.
-- Fernando Pereira
------------------------------
Date: Thu 26 Sep 85 15:20:03-PDT
From: Fernando Pereira <PEREIRA%sri-candide@sri-marvin>
Subject: Destructive Assignment
Rick McGueer seems to be confused about the differences between
structure sharing and non-structure sharing methods of term
representation in Prolog. In both methods, if we want to ``change''
an argument of a functor, say `a' by `b' in f(X,a,Y), what Prolog
copies is a chunk of c*n+k cells where c and k are implementation
-defined constants and n is the arity of the functor. When replacing
a subterm at depth m of a term t, the number of cells copied is
sum(i=0..m-1,c*n_i+k) where n_i is the arity of the functor at depth
i. If the data structures are kept well balanced, it follows that
the cost of updating a term of height m is O(log m). Of course,
this is just a particular case of the fact that a random-access
memory of size s can be simulated by assignment-free data structures
at an overhead of O(log s). In applications I have developed, this
overhead is a small cost to pay for ease of programming and the
space recovery efficiencies inherent in the stack allocation used
by any reasonable Prolog.
-- Fernando Pereira
PS: Cf. discussions on arrays in Prolog in earlier Digests, the
paper ``Incorporating Mutable Arrays into Logic Programming''
by Lars-Henrik Eriksson and Manny Rayner, and David H. D.
Warren's logarithmic array code in the collection at
SCORE:<PROLOG>
------------------------------
Date: 26 Sep 85 23:58:16 PDT
From: Deutsch.PA@Xerox.ARPA
Subject: Destructive Assignment
Again, I would like to suggest a different view of assignment
than Rick McGeer's last comment. If A is embedded in B, C, and
D, the routines manipulating B, C, and D don't need to know
anything at all about the structure of A: all they need to know
is that they have to embed the modified A in their own structure
in the appropriate place, namely the place they got it from in
the first place to be able to tell it to modify itself. Whether
a language has abstraction is independent of whether it has
assignment. I consider Prolog's lack of abstraction and
modularity a much more serious problem for its use in systems
than its lack of destructive assignment.
------------------------------
Date: Fri, 27 Sep 85 10:32:44 PDT
From: (Rick McGeer) Mcgeer%ucbkim@Berkeley.EDU
Subject: Destructive Assignment, again...
Your argument is well-founded, but the principal argument for
destructive assignment is modularity, not efficiency. Consider
two data structures, A and B, that share some common substructure
C. Now, if C is modified, a new copy of C, C' is created. In
most applications, one wants the data structures A and B to
contain the new substructure C'. Am I wrong in believing that A'
and B' must be created in the absence of destructive assignment,
since both A and B are now outdated? And if I'm correct, isn't
it also the case that the parents of A and B must also be modified,
and so on recursively.
If program data structures were treelike rather than networklike
(in short, if no two data structures shared common substructure),
then copying is reasonable since one assumes that the only method
of accessing substructure is through the root of the tree, and
superstructures can be appropriately modified through the accessing
traversal. If data structures are networklike, the problem is harder,
since the access to the substructure can come through one of a number
of parents, which means that the code which modifies the substructure
must be able to access all the parents of the substructure, and so on
through the data structure.
My own programs tend to shared structure a fair amount, which is why
I'm banging away at this problem. It turns out that there's a way
to hack the moral equivalent of destructive assignment into Prolog
(using lists with unbound cdrs), but this requires time O(n) for a
set or access, where n is the number of times that this variable has
been set...
Anyway, if I'm confused about this, I'd appreciate any pointers that
you have to programming techniques to avoid the problem of shared
structure.
-- Rick.
------------------------------
Date: Fri, 27 Sep 85 15:39:51 PDT
From: (Rick McGeer) Mcgeer%ucbkim@Berkeley.EDU
Subject: Destructive Assignment, again
Yes, I thought of that, too. I rejected it because it seemed
to defeat one of the central purposes of symbolic languages,
namely getting rid of explicit pointers. Further, after examing
the Warren PLM I couldn't think of a good way to do this invisibly
without major surgery to the PLM. Destructive assignment, however,
required only oen new instruction (rplacarg), and modifying the
trail to contain 2 longwords per entry rather than one.
-- Rick
------------------------------
Date: Fri, 27 Sep 85 13:44:33 PDT
From: Deutsch.pa@Xerox.ARPA
Subject: Destructive Assignment, again...
Thanks for your thoughtful reply. As you point out, the natural
underlying structure of the data may be an unrestricted graph,
for which I don't know how to construct a purely functional
representation that models edges as pointers. However, it's
easy to construct a functional representation that doesn't model
edges as pointers: divide the structure up into a set of nodes
represented by unique ids, and a separate dictionary that maps a
node id to the contents of the node it represents. This
representation caters nicely to the problem of updating an
interior node and having the update visible from anywhere that
references it. In effect, a level of indirection has been
introduced. While the dictionary itself must be global to the
structure involved, it doesn't have to know anything about the
semantics of the individual nodes or edges, so logical modularity
is still preserved. And the indirection can be covered with
syntactic sugar to eliminatemost of the burden on the programmer:
all that is necessary is that node references be represented as
pairs <containing structure, node identifier>, and that all node
updates return a new containing structure with appropriate
modifications. All that remains is to make sure the garbage
collector knows it can remove any dictionary entries where the
id isn't accessible -- in effect, knows that the dictionaries are
being used to simulate a memory system.
In circumstances where the natural structure of the data is not an
unrestricted graph, pointers can be modelled as pointers, and
reconceptualizing the algorithms to use paths or indices rather
than direct references may yield more transparent programs. (It's
been my experience that a lot of the bugs that arise in systems are
the result of implicit transmission of side-effects through sharing
of references to mutable structures.)
There have been a number of papers in the Lisp / Functional
Programming symposia on the subject of effective programming
without side effects. That would be the first place I would
look for references.
------------------------------
Date: 27 Sep 85 18:05:34 PDT
From: Deutsch.pa@Xerox.ARPA
Subject: Destructive Assignment, again...
Wait a minute. Surely destructive assignment implies the
existence of "reference" as a concept that is visible to
the programmer? And how is this different from "explicit
pointers"? In a functional language, the concept of
"reference" disappears -- you can't tell the difference
between eq and equal (and in fact the implementor is free
to adopt strategies that may copy or share, ad lib.) The
dodge I suggested simply makes references explicit in those
(and only those) places where their semantics are needed.
In Prolog, logical variables create a kind of sharing that
is pretty much just like a reference. In this respect Prolog
feels quite different to me than a functional language. On
the other hand, there may be a way to think of Prolog clauses
as functions from environments to environments that is more
like what I suggested. Also, in principle the Prolog
implementor is free to use a mix of copying and sharing
strategies (e.g. Prolog on a multi-processor will probably have
to do some copying), as long as the equality constraints between
occurrences of a given variable are extended to include any
copies.
------------------------------
End of PROLOG Digest
********************