PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (10/17/87)
PROLOG Digest Sunday, 18 Oct 1987 Volume 5 : Issue 74
Today's Topics:
Announcement - European Perspective & QB1,
Implementations - Argument & Types & Failure & Badness
----------------------------------------------------------------------
Date: Thu, 15 Oct 87 13:34:53 EDT
From: finin@bigburd.PRC.Unisys.COM (Tim Finin)
Subject: PROLOG AND AI APPLICATIONS - A EUROPEAN PERSPECTIVE
AI Seminar
UNISYS Knowledge Systems
Paoli Research Center
Paoli PA
PROLOG AND AI APPLICATIONS - A EUROPEAN PERSPECTIVE
Raf Venken
BIM Prolog
Raf Venken, manager for BIM Prolog Research and Development, will be
visiting Logic Based Systems on Monday, October 19th. BIM is a high
performance Prolog which runs on UNIX-based SUN workstations as well
as VAXES under VMS, UNIX 4.2, and ULTRIX. BIM is involved in joint
research efforts with various universities throughout Europe and is a
member of ESPRIT (the "European MCC"). BIM has also contributed to
LOQUI, a large natural language project.
BIM claims to be the fastest general purpose Prolog system currently
available on the market. BIM includes "the first successful attempt
to include more intelligent debugging aids into the [Prolog] system"
and a "PARTIAL EVALUATION system which optimizes Prolog programs by
source-to-source transformations." BIM has also "extended the Prolog
language with the concept of MODULES to allow the easy development of
very large systems."
The talk will cover the philosophy and strategy behind BIM Prolog,
discuss current ESPRIT projects including a large NLP system, and
speculate about the future.
11:00am, Monday, October 19th
Cafeteria Conference Room
- if you are interested in attending, please send -
- mail to finin@prc.unisys.com or call 215-648-7446 -
------------------------------
Date: Thu, 15 Oct 87 15:13:18 EDT
From: finin@bigburd.PRC.Unisys.COM (Tim Finin)
Subject: OB1: A Prolog-Based Object-Oriented Database
OB1: A PROLOG-BASED OBJECT-ORIENTED DATABASE
Benjamin Cohen
SRI International
David Sarnoff Research Center
Princeton NJ 8540
In this talk I describe OB1, an object-oriented database facility. OB1
is a hybrid query language that incorporates most of the features of
relational query languages plus "view/objects" that allow sets as
values and recursive views. OB1 is implemented in Quintus Prolog and
includes server facilities that allow C & Fortran clients to query an
OB1 server over a SUN network. OB1 also has a graphics
Entity/Relationship data modeling editor used to design OB1 databases.
Ben will be here friday, October 23, from lunch time till 5 - I suppose
the talk would start around 1:30 or 2:00
2:00pm Friday, October 23
Cafeteria Conference Room
- if you are interested in attending, please send -
- mail to finin@prc.unisys.com or call 215-648-7446 -
------------------------------
Date: Thu, 15 Oct 87 12:08:29 BST
From: Fernando Pereira <pereira%cam.sri.com@drakes.ai.sri.com>
Subject: Inappropriate arguments, failure and types
In his latest communication about Lagache's library, after comparing
various Prolog versions of "merge" with an ML version, Richard O'Keefe
makes the comment
PROVIDED that this was documented as ONLY being usable to
compute the third argument from the first two, this would be
tolerable.
Mind you, I find it extremely odd that
merge([], [a], X)
would be reported as an error, but that
merge([], a, X)
would NOT be reported. What is so special about wrong length that
it is the only error that deserves reporting?
It is interesting to note that this problem does not arise in the ML
version, because ML's type system will reject the equivalent ML function
call, since "a" is not a valid list constructor. Now, there's a simple
but rather subtle point here. Even though EXTENSIONALLY a function
is just a special case or a relation, functions in a typed functional
language like ML are always given with their domain and range. In the
ML type system, the type specification
merge: Alpha list x Alpha list -> Alpha list
states that for ANY type Alpha, "merge" guarantees to take any pair of
lists of elements of Alpha to a list of elements of Alpha, PROVIDED
that it terminates. That is, "merge" will not return an object outside
its declared range if it is given objects in its declared domain.
However, the ACTUAL extension of "merge" as defined is smaller, that is,
"merge" is a PARTIAL function from its declared domain to its range.
Operationally, partiality may correspond to exceptions (in the present
example two lists of different lengths) or to nontermination.
One could of course conceive of a richer type system in which "pair
of lists of Alpha with the same length" would be a definable type; "merge"
with such a domain would be total. Unfortunately, in type systems
more fine-grained means less tractable. Clearly, the unsolvability
of the halting problem ensures that with a decidable type system some
functions will partial on their alleged domains. The lesson I want
to draw from these observations is that functions don't "have" types,
rather types are GIVEN to functions as an indication of what the functions
are guaranteed NOT to do: namely, not to return values outside their
range when they are given values in their domain; typecheking is
a means of ensuring that type assignments are consistent.
When we move from functions to relations, things become even less clear.
Whereas one might say that IDEALLY a function should be total on its
declared domain, it's just that the unsolvability of the halting problem
prevents us from giving it the right type, relations are not INTENDED to
be total. What's involved here is a decision as to what properties of
a relation are taken to be NECESSARY and what properties are taken to
be CONTINGENT. For example, we may take it to be necessary that the
"is a divisor of" relation relates integers, but contingent that
7 has no positive divisors except 1 and itself. Then we would argue
that using the relation with non-integer arguments is a "type error"
whereas using it with arguments 3 and 7 is a valid question that just
happens to fail. This issue comes up also in distinguish between
"nonsense" and "falsity" in English statements. As in this case,
the distinction is mostly governed by the intentions of the participants
in the dialogue. Whether "No rock owns a car" is seen as nonsensical
or just trivially true has to do with the states of mind of participants
in the communication act and what they intend to achieve by communicating.
The lesson that I draw from these observations is that one should
distinguish the actual EXTENSION of a relation, as given by its
definition, from its intended domain of applicability as given by
comments or type declarations. The use of "defensible" explicit
failure clauses is redundant and confusing. Predicates SHOULD just
fail if they are given arguments outside their extension; if programmmers
require additional help in recognizing situations where a call
will because its arguments fall outside its intended domain of use,
tools like the O'Keefe-Mycroft typechecker could be used., or indeed
good old-fashioned paper-and-pencil logical reasoning. That is,
typechecking should be seen as an aid to program verification: type
declarations state intended properties of relations (eg. that
if the first two arguments of "merge" are lists the third argument
will also be a list is "merge" succeeds), and type checking verifies
whether the actual program satisfies those (partial) specifications.
-- Fernando Pereira
------------------------------
Date: Fri, 16 Oct 87 23:43:13 PDT
From: quintus!ok@Sun.COM (Richard A. O'Keefe)
Subject: Why so much bad Prolog?
One reader of the Prolog Digest, having seen my recent messages
about some common systematic errors in Prolog programs (if any
of you thinks I think Lagache's code is particularly bad, know
that you are wrong! He has enough comments so that I can see
what he means. That excuses a great deal.) asked me whether I
had any idea why there is so much bad Prolog code around.
I was all set to spout, but it dawned on me: is there any
evidence that Prolog programs tend to be any worse relative to
the obvious canons than programs in any other language? I'm
beginning to wonder. We installed the "news" system recently.
It's great to read articles about C and UNIX and Lisp again.
But two things strikes me forcibly:
Many people sending messages to net.lang.c and the
like know little about spelling and care less.
An amazing number of them seem to have no acquaintance
with English or American grammar. (The two differ:
for example American has "get off of the chair" and
verb-noun modification "walk shorts". English has
neither of these. I'm not complaining about differences
from English grammar; this is America.)
Dijkstra has said that he thinks the two most important
prerequisites for a programmer are a mastery of one's native
language and an aptitude for mathematics (as opposed to having
extensive knowledge of mathematics). I think he is right.
Both of these attributes can be seen as
- caring about getting things RIGHT
- a feeling for rule-governed systems
Dijkstra isn't the only one. H. Beam Piper, in one of the two
"Little Fuzzy" books he completed, has Judge Pendarvis say "It's
all the fault of the English teachers."
"Aptitude for mathematics" shows up in two areas that tend
not to receive much attention: boundary cases and ensuring
that program parts fit together with a minimum of sticky tape.
Someone who would be comfortable thinking in terms of algebras
(even if s/he has never heard of them) will want to ensure that
routines do something sensible with any argument, and will want
to ensure that the outputs and arguments of various pieces are
compatible so that s/he can think in terms of composing operations.
Most of the programs I have seen in any programming language
are rather bad. This even applies to code published in journals
and conferences. I could give examples, but there are libel laws
in this country... Nearly all the C code I have seen was quite
amazingly ugly. If you are using UNIX, you might try using the
look(1) command on a file with very long lines.
/usr/bin/look fred /vmunix
is a good one to try. There are other UNIX commands that are
likely to crash with long lines. I think the worst "published"
code I have ever seen was in the UCSD P-system user-contributed
library. There were programs in that that weren't even FINISHED.
One of the important things you have to realise if you want
to write good code is that you aren't already doing so. We might
list this as another attribute for a programmer
- ability and willingness to regard one's own work critically
Someone who never pulls back from the terminal saying "wait a minute,
this is just too ugly, I must be doing something wrong" is almost
certainly doing something wrong and writing ugly code. It is
necessary to criticise one's own code no matter how expert one thinks
one is in the programming language one is using: there is often a
better algorithm, one may be doing something inconsistently in
different places (e.g. UNIX command options...), it might be better
to write an interpreter, ...
It is also necessary to realise that you never stop learning the
things you can do with your programming language. I've been writing
C for years, and yet only this week I was shown a technique which,
now I've seen it, is obvious, powerful, and about as elegant as C
ever gets. So it is always worth taking a step back from a WORKING
program and asking "could I express that more clearly?"
But criticism of the quality of the code is perhaps a fine point.
Correctness is more important, and here it is vital to be "scientific"
about your code. It is not enough to say "how can I see if this is
working". You have to ask "how can I *break* it?" One of the reasons
why Quintus Prolog is as reliable as it is is that we are continually
looking at the code and asking ourselves "how can I break that?". All
too often there is a way, and we fix it. Sometimes the fix is a hack,
but then the fix often needs fixing later because it doesn't work in
another operating system or whatever. Good fixes make things simpler.
If there IS a special problem with Prolog, I think it is probably
due to the fact that Prolog is DIFFERENT. If you already know Lisp,
SNOBOL or Icon, a pure functional language, and a data base query
language, then Prolog is just more of the same. But if you are a
Pascal programmer, you tend to think you know all about structured
programming, and if the habits that the straitjacket of Pascal has
crippled you into don't work too well in Prolog, you tend to think
that it's Prolog's fault. Wrong. The key point about Prolog is that
the PURE things are fast and the imperative things are slow, which is
the direct opposite of languages like Pascal.
It doesn't really help that a lot of people out there are making
a fast buck writing Prolog textbooks that don't even tell you how to
design a collection of predicates to be managed by assert/1 and
retract/1. They tell you what the operations do (sketchily), and
then leave you on your own as to how to use them. (The answer, by
the way, is to study the data-base literature. Update anomalies
are quite as important in Prolog as in relational databases, and
have the same causes. You also need to bear in mind the difference
between universal and existential null values, and the fact that a
logical variable is a UNIVERSAL null, not an existential one, which
means that using logical variables for nulls is almost always wrong.)
Who will teach the teachers? Until we have more Prolog textbooks
that are at least as good as Sterling & Shapiro or Pereira & Shieber,
we must EXPECT people to write bad Prolog code.
May I suggest that it would be useful to have people commenting
on their experiences with Prolog textbooks in this digest? It would
be particularly good to find out what the worst gaps are. setof/3
and bagof/3 are one obvious example: Sterling & Shapiro are easily
the best about that, and they are a wee bit shaky; Bratko is
seriously misleading. Are there any books which point out that
Definite Clause Grammar rule are a practical tool for list processing
generally, not an esoteric thing exclusively for natural language
processing? Does your favourite textbook tell you that the Prolog
convention is to call 'nl' at the END of lines? (Some programmers
do it at the beginning, which doesn't work too well with other UNIX
or VMS utilities.) Have you ever needed a sorting routine other
than the built-in sort/2 and keysort/2, and did your favourite
textbook tell you that the best general purpose sorting routine
in Prolog is merge sort; did it tell you how to write a merge sort?
Would you like me to tell you?
------------------------------
End of PROLOG Digest
********************