PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (01/29/86)
PROLOG Digest Thursday, 30 Jan 1986 Volume 4 : Issue 6
Today's Topics:
Implementation - Coding Algorithm & Syntactic Sugar & NAIL!,
LP Philosophy - What is the Expressive Power of Prolog?
----------------------------------------------------------------------
Date: Tue, 28 Jan 86 15:56:30 pst
From: Allen VanGelder <avg@diablo>
Subject: median algorithm in Prolog
In Kale's algorithm for median (see Issue 5) the "choose"
rule divides by 2, when it apparently should divide by 7.
Incidentally, the correct way to divide Length_S by K and
round up if there is any non-zero remainder is:
N is ((Length_S + K - 1) // K)
provided you know Length_S is nonnegative, of course.
Now for the real test of Prolog's usefulness (CHALLENGE,
CHALLENGE!): Modify the program to lower the constant
factor, by "remembering" the results of comparisons done
in "medians" i.e., the results of sorting sublists of length
7. Avoid repeating those comparisons in "partition".
The test of a well designed program is that such enhancements
can be done with reasonable effort, re-using most of the
original code.
Run some tests to see if this really saves time on sets of,
say, 200 items. Does the cost of comparing two items enter
significantly? I.e., does it matter whether we compare
integers or arbitrary terms?
------------------------------
Date: Tue, 28 Jan 86 15:23:33 pst
From: Allen VanGelder <avg@diablo>
Subject: More syntactic sugar for Prolog
Zerksis commented on Prolog's if-then-else in Issue 5. I will
comment on two points not mentioned there.
The first point not mentioned is that
(P -> Q ; R)
will not backtrack thru P, if implemented as advertised --
i.e., equivalent to
(P, !, Q; R)
In other words, if P has several solutions, Q had better need
only the first one.
To me, the more consistent implementation would be equivalent to
(P, Q; \+ P, R)
where \+ is the "finite failure not."
Consequently, we are defining it this way in NAIL, a logic
programming language under development at Stanford CSD.
The second point is that (P -> Q ; R) is parenthesized as
((P -> Q) ; R)
which is not what one would expect, reading ";" as "else" in this
setting. The NAIL syntax is
(P -> Q else R)
That is, "else" is a binary operator that is TIGHTER than "->"
(whereas ";" is LOOSER than "->"), so that the above expression
is parenthesized as
(P -> (Q else R))
as one would expect.
I agree with Zerksis on the desirability of providing constructs
that reap the efficiency benefits of cuts, so that "raw cuts" can
be done away with. NAIL's if-else does this (Prolog's doesn't).
Zerksis' cut-free case structure might allow greater efficiency,
but it needs an ambitious interpreter or compiler. The cut
simulating case structure retains the undesirable semantics of the
cut, however, so I would steer away from it.
------------------------------
Date: Wed, 29 Jan 86 10:20:22 pst
From: Allen VanGelder <avg@diablo>
Subject: Quick summary of NAIL
NAIL is a research project one of whose goals is to determine
what degree of expressiveness and efficiency can be obtained
by a logic based language without resorting to certain
"undesirable" non-logical mechanisms such as cut, assert and
retract, rule order, and subgoal order. Jeff Ullman, the PI,
likes to draw the analogy:
"NAIL is to Prolog as Relational DBMS is to CODASYL."
NAIL is in a preliminary stage of development at Stanford CSD.
An overview, "Design overview of the Nail! System" is available
from Professor Ullman.
NAIL! is an acronym for "Not Another Implementation of Logic!"
------------------------------
Date: Tue, 28 Jan 86 11:37:43 PST
From: Deutsch.pa@Xerox.COM
Subject: Expressive power
I would like to disagree with the final points in Fernando
Pereira's argument about "machine power" and "expressive
power".
Our inability to build reliable software products is not due to
lack of machine power in our tools (we have had plenty ot that...)
but to our inability to predict the interactions between components
for which there are no good abstract specifications and implementa
-tions. The practice of Lisp programming shows this clearly. Current
logic programming tools are somewhat better, but clearly not good
enough, particularly with respect to modularity.
First, for "Lisp" one can substitute any other existing language --
including Prolog. What I have seen of the logic programming
literature does not support the implicit assertion that people
write "good abstract specifications" for logic programs in practice
more often than for other kinds of programs. Indeed, the practice
seems to be the opposite -- people seem to say "logic programs are
self-documenting and so transparent that abstract specifications
are unnecessary". Furthermore, Prolog has no support for data
abstraction -- Prolog data structures are typically lists or terms,
which correspond precisely to the lists/sequences/arrays and records
of conventional languages (or Lisp). Also, as Pereira observes,
Prolog (like Lisp) has no modularity, which I believe has proven
to be one of the most powerful constructs for organizing large
systems of programs. Finally, it has been observed many times that
large-scale (system-scale) programs exhibit problems that are
qualitatively different from those of small programs or algorithms.
The logic programming literature that I have seen is only about
small programs. Because of this, I think comparisons of Prolog
and anything else from a software engineering standpoint are not
appropriate.
------------------------------
End of PROLOG Digest
********************