restivo@POLYA.STANFORD.EDU (Chuck Restivo) (07/08/88)
Date: Wed, 4 May 1988 0:4:41 PST
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@POLYA.STANFORD.EDU>
Reply-to: PROLOG@POLYA.STANFORD.EDU>
US-Mail: P.O. Box 4584, Stanford CA 94305
Subject: PROLOG Digest V6 #27
To: PROLOG@POLYA.STANFORD.EDU
PROLOG Digest Friday, 1 Apr 1988 Volume 6 : Issue 27
Today's Topics:
Implementation - Trilogy & Destructive Assignments,
& Simple Problem & end_of_file,
& BSI Standard & A Wager
----------------------------------------------------------------------------------------------------------------------------
Date: 23 Mar 88 19:44:15 GMT
From: pacbell!att-ih!alberta!ubc-cs!voda@AMES.ARC.NASA.GOV (Paul Voda)
Subject: Compilation in Trilogy
Here is the answer formulated in a slightly more general setting:
The modes and types of Trilogy permit the native code compilation
of programs in such a way that there are no run-time tags on
most of the values, neither there are any reference counters.
The decision when to copy out and when to share the
values of input-output variables is done by a compile
time data-flow analysis. Similarly, the compiler of Trilogy checks whether
the output variables are assigned values in all branches of a predicate
(whether all input-output variables are initialized). There
is also a check to see that if-then-elses do not backtrack
(either before thens or among the branches), e.g.
if x = 1 | x = 2 then
x <> 1 & P(x)
else
......
end
The above is dissalowed by the compiler if x is output or
symbolic (logical), but is OK if x is input or input/output.
Thus we can guarantee that the negation of the formula
before a then is always properly computable.
Consequently if-then-elses and the formulas before thens
are compiled without any settings of choice points. We are
just releasing a version where non-backtracking ors (|)
(implemented by jumps instead of choice points) are permitted
in procedures (this is useful for the writing of the Trilogy
counterparts of Pascal's boolean functions).
There are two situations where the run-time tags on Trilogy values
are present:
1) the tags discriminating the union values, these should
be also present in Pascal programs.
For instance, the universal type U of all Trilogy's values has a
form of a union:
U = R(R) | S(S) | P(U,U)
The tags R(eal), S(tring), and P(air) are thus present in the
values of U variables.
If a value is not of a union type (tuple, list, array,
integer, enumerated-type etc.) then it contains no tags,
except of course the tags of any of its union constituents.
2) When a variable is of symbolic (logical) mode then Trilogy
uses the type specific tags to identify the constraints
attached to the variable (=, <, <>, etc.).
Because of the typing, modes, pred/proc modifiers and a quite extensive
data-flow analysis the compiler of Trilogy produces a procedural
code of Pascal-like quality while offering all the high-level
comfort of symbolic values with their associated constructors
and destructors as we know it from Prolog.
------------------------------
Date: 16 Mar 88 23:35:51 GMT
From: sanjay@arizona.edu (Sanjay Manchanda)
Subject: Logic of Database Updates
I have worked on doing database updates in Prolog in a "logical"
fashion. A database update is essentially an assignment on the
database. If we are going to update the database, why not first
develop a logic for reasoning about database assignments, and then
mechanize it in the true logic programming tradition? A dynamic
logic is a reasonable choice for this task, since dynamic logics
were developed to reason about programs which explicitly manipulate
their state (i.e. do assignment). I have developed a dynamic
logic for reasoning database updates that doesn't look much like the
dynamic logic's that you may have seen, but it leads to a simple
extension of Prolog.
Instead of going into the logic, I will briefly explain the extension of
Prolog. Richard introduced it rather well in a previous
message, so let me borrow some of his words.
>Roughly speaking, there are three classes of predicates:
>
> pure predicates (don't depend on things that change)
>
> state predicates (depend on things that change, but change nothing)
>
> transition (or dynamic) predicates (express a relation between states)
>
>For example, we might say
>
> p(X) :-
> <-fred(X)> q(X).
>
>p(X) is true in a world W if there is a world W1 such that
> -(fred(X), W, W1) -- roughly, retract
>and q(X) is true in W1.
>
>Note that this doesn't change W.
There are two sets of predefined dynamic predicates, +p and -p for
every pure predicate p. Actually, to avoid some thorny
implementation and semantic problems, p is restricted to be a pure
predicate that is defined entirely by ground Prolog facts. For
obvious reasons, such a predicate is called a database predicate.
New dynamic (or transition) predicates can be defined by means of
Update Rules. For example, we might say
add_flight(Fno, Src, Dest) <--
airport(Src), airport(Dest),
<+flight(Fno, Src, Dest)>.
The use of the `<--' instead `:-' signals that a dynamic predicate is
being defined. Here the semantics of add_flight(Fno, Src, Dest) is
a transition from a world W to a world W1, such that (airport(Src),
airport(Dest)) is true in W, and W1 is obtained from W by adding
the fact flight(...) to W. Thus, viewed as an operator, + is
roughly equivalent to assert.
The rule may be used in a top level query like:
:- <add_flight(20, 'LA', 'OHARE')>reachable('LA', 'JFK')
which is true in a current world W if there exists W1 accessible
through the meaning of add_flight(..), and reachable('LA','JFK') is
true in W1. Assume that reachable is the transitive closure of the
flight relation. The execution of the query is not very different
from Prolog execution. Thus the call <+flight(..)> will return a
new (world) database in which reachable(...) will be evaluated. If
this evaluation fails, backtracking will cause the inserted fact
flight(...) to be removed. Similarly, deletion on the database is
undone on backtracking.
If the query succeeds, it will return a new updated database and
display to the user, all the changes that have been made to the
current database. The user can then choose to commit these changes
and make them permanent, or reject them and leave the database
unchanged.
The language has a well-defined declarative semantics, and a syntax
that reflects this semantics. This makes it considerably better
than using assert and retract for database updates. As an example,
note that in my proposed extension, updates are statically scoped.
If p(X) is pure predicate or a state predicate, the database is
guaranteed to remain unchanged after it is executed. This can be
quite significant for compiler and database query optimization.
I did not allow updates to rule-defined predicates because I wanted
to guarantee that (not p(a)) was true after executing <-p(a)>.
However, I think that can extend the treatment if I use a weaker
semantics. I will mail copies of [1], [2] and [3] to anyone who
requests them. My apologies to Richard for forgetting to mail him a
copy of my paper.
-- sanjay
References:
[1] Sanjay Manchanda and David Scott Warren.
A Language for Database Updates.
In Jack Minker, editor, Foundations of Deductive Databases and
Logic Programming, Morgan-Kaufmann, Los Altos, CA, 1987.
[2] Sanjay Manchanda, Soumtira Sengupta, and David S. Warren.
Concurrent Updates in a Prolog Database System
Technical Report 86/28, Department of Computer Science,
SUNY at Stony Brook, Stony Brook, NY 11794,
December 1986, Revised Feb 1987.
[3] Sanjay Manchanda
A Dynamic Logic Programming Language for Relational Updates.
Phd Thesis, SUNY at Stony Brook, Stony Brook, NY 11794, December
1987.
------------------------------
Date: 17 Mar 88 03:49:59 GMT
From: munnari!vuwcomp!lindsay@uunet.uu.net (Lindsay Groves)
Subject: mine embarrassingly simple problem
I'll save Richard saying it -- this doesn't say much about the program, and
certainly doesn't explain why ancestral cuts are supposed to be necessary.
Could you describe the problem in a bit more detail and illustrate just
how the need for ansectral cuts arises? Perhaps a simplified version of the
problem could be used to illustrate the point. An example would certainly
help.
-- Lindsay Groves
------------------------------
Date: 23 Mar 88 01:16:54 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: mine embarrassingly simple problem
In that case, why not just code it as
map(Function, Network) :-
generate(Function, Network),
test(Network),
!.
test(Network) :-
lemma(Network, StopCondition).
More generally, suppose that you had several cases:
test(Network) :-
lemma(Network, ~~~),
!(map(_,_)),
p(...).
...
test(Network) :-
lemma(Network, ~~~),
!(map(_,_)),
q(...).
Then you could recast this as
map(Function, Network) :-
generate(Function, Network),
test(Network, Continuation),
!,
finish(Continuation, ...).
finish(p, ...) :-
p(...).
...
finish(q, ...) :-
q(...).
test(Network, p) :-
lemma(Network, ~~~).
...
test(Network, q) :-
lemma(Network, ~~~).
The basic idea is to redesign your "test" code so that it breaks into
three pieces: before-the-cut, the ancestral cut, and after-the-cut,
and then unfold the call to it so that the cut is exposed in "map".
------------------------------
Date: 20 Mar 88 20:55:02 GMT
From: lagache@violet.Berkeley.EDU (Edouard Lagache)
Subject: My views on developing a PROLOG standard
To help get the creative juices flowing on those position papers,
I thought I would throw in my two cents worth on this proposed
standard.
While I am not really qualified to make much commentary on the
subject (So what? that has never stopped me before!), there are a
number of peripheral matters that I would like to see addressed.
The matter of greatest concern for me is the question of whose
standard will be the standard? The BSI group is a British standard;
Now I hear that the French are working on their own standard (the AFNOR
group). All this is fine and good except that in all likelihood the
resulting standards will have about as much similarity with each other
as the French and English (natural) languages do (never mind the fact
that neither standard will have have much to do with existing practice)
- This is progress!?!
Perhaps this is a wild fantasy on my part, but I would really
like to see ONE (1) standard. That standard should be agreed upon not
just by the British and the French, but by ALL the major users of
PROLOG which includes (at the very least) most of Europe, Japan, and
the U.S. It seems to me that someone should bug the ANSI standard
committee, NOT to come up with their own standard (Lord have mercy on
all those "C" and FORTRAN users once the new standards are in place),
but to take part in an international effort to come up with the before
mentioned 1 PROLOG standard.
Fantasies aside, I do have a few comments on the BSI standard. On
the specifics of the "grimoire", I can only steal a quote from the
venerable Michael Clancy: "Do the right thing". In this case, "Do the
right thing" means try to capture existing practice as much as possible
(see "lots of smoke" on exactly what existing practice means on the
FORTRAN SIG). I do believe that asking the question of how existing
code would run under the new standard is a valuable measure of the
success at capturing existing practice. Unless there is a *strong*
reason to change syntax, the new standard shouldn't depart from
existing practice. Thus, I have read Richard O'Keefe's comments on his
perceptions of the standard syntax with real concern. Until I see a
"reasonable" reply from the standards committee, I am inclined support
Richard O'Keefe's position on this matter.
At the end of last week there was some discussion of the standard
library. Here I have one suggestion, make the library big enough so
that people don't have to reinvent the wheel all the time. I took a
lot of heat for my imfamous PROLOG libraries, while the code quality
was perhaps inadequate, I believe that the concept was valuable. Even
in as rich a language as Franz LISP, I still found the need for 1600
lines of additional general purpose functions. So there is a lot of
room expansion in PROLOG.
I would like to suggest defining a separate set PROLOG libraries,
much in the same way the UNIX "C" library is (was?) defined
independantly of the language. In this area, I would strongly suggest
various levels of libraries. There should be some core set that would
be required for the standard language, then additional standards would
be defined for supplemental libraries. <*Fantasy mode on*> Ideally
the standards committee should provide source code for those
supplemental libraries in the core standard language (when possible),
so that anyone using any standard PROLOG implementation could use the
full set of libraries (if more slowly than if all the predicates were
builtin). <*Fantasy mode off*> In any case, Everybody knows that the
first thing PROLOG system implementors do is to embellish on the
standard core library, so wouldn't it be nice if the standard included
a few hundred predicates to keep those implementors busy upgrading
their product in a standard way (maybe I should have kept Fantasy mode
on?)
The last thing I would really like to see is some vast
improvement in the standard user interface tools. Even if not all
hardware can support it, I would like to see some standard way to
access windows, i/o devices (i.e. mice), and or forth. If one could
write complete applications in PROLOG that had portable "bells and
whistles", that would make PROLOG much more attractive for those trying
to make polished products for end users, since that would greatly reduce
porting problems (I know, Fantasy mode is still on!)
Still dreaming in California,
-- Edouard Lagache
------------------------------
Date: 23 Mar 88 01:09:49 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: My views on developing a PROLOG standard (long but fun!)
Wrong. Roger Scowen of NPL get the thing started; since the NPL is in
England he naturally got the thing started as a BSI project. AFNOR are
not developing a rival standard; they have been collaborating with the
BSI group for a long time now, and the Formal Specification is French work.
(While many people will find it the most confusING part of the BSI material,
it is arguably the least confusED.) The whole thing has now become, I hear,
an ISO "work item", and the more recent BSI documents bear ISO reference
numbers.
> That standard should be agreed upon not
> just by the British and the French, but by ALL the major users of
> PROLOG which includes (at the very least) most of Europe, Japan, and
> the U.S.
Hear hear. And don't forget the South Pacific (home of NU Prolog and CLP)
or Israel (home of Wisdom Prolog).
> I took a
> lot of heat for my imfamous PROLOG libraries, while the code quality
> was perhaps inadequate, I believe that the concept was valuable.
Too right.
> The last thing I would really like to see is some vast
> improvement in the standard user interface tools. Even if not all
> hardware can support it, I would like to see some standard way to
> access windows, i/o devices (i.e. mice), and or forth.
I understand that agreement on the Common Lisp binding for X is at least
a year away. Plagiarism being the sincerest form of flattery, I suggest
that it might be an idea to wait for the Lisp people to do the work, and
then transliterate as much of it as possible. Or would a 'curses'
binding be of more immediate use? Either way, I don't see any need for
a standard way to access Forth; Postscript maybe, but not Forth (:-).
-----------------------------
Date: 21 Mar 88 09:26:04 GMT
From: nsc!taux01!shahaf@decwrl.dec.com (Shahaf Moshe)
Subject: mine embarrassingly simple problem
First I would like to make two comments:
* I am a NOVICE (in Prolog).
* I do not claim that in my application Ansectral Cut are a MUST. I wrote it on
a system were it was a feature and I used it. Since its not available in
Quintus Prolog, I asked for help.
About the application,
The program looks for best mapping of a Boolean function onto a set of logic
primitives such as
X * Y * Z maps to: 2inputAnd( 2inputAnd( X, Y) , Z)
or: 3inputAnd( X, Y, Z)
Since the search space is huge I used Ansectral Cut to abort
mapping once I get some "STOP CONDITIONS".
The program looks like:
map(Function,Network) :-
generate(Function,Network),
test(Network).
test(Network) :-
lemma(Network,StopCondition),
!(map). %this cut aborts the process.
I hesitate to post longer description on the net. If anyone would like to
get more elaborated data I will mail upon request.
------------------------------
Date: 19 Mar 88 03:04:08 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: behavior of read/get0 at end_of_file
I thought you might be interested to know what the BSI committee say.
In document PS/236, "Draft minutes, Prolog Built-In Predicates meeting,
10 December 1987", we find
4 Design criterion
<name deleted> suggested: "Whenever possible, a predicate with
a side effect should always succeed and never instantiate
variables."
This of course rules get0/1 and read/1 out entirely. That may not be
what <name deleted> _meant_, but it _is_ what the minutes say he _said_.
As far as I can tell, the real intent is to rule out retract/1, which
is disliked because it unifies its argument with the thing you removed.
The minutes show that Paul Chung proposed naming the standard clause-
removing predicate delete/1 instead of retract/1. Good on yer, mate!
This should not be construed as endorsement of the name delete/1, but
as praise for Paul Chung's good standardisation manners.
------------------------------
Date: 22 Mar 88 15:56:23 GMT
From: mcvax!unido!ecrcvax!micha@uunet.uu.net (Micha Meier)
Subject: behavior of read/get0 at end_of_file
This is true, we have to distinguish various uses
of get0/1. The above example is indeed easier
written when get0/1 fails at the eof, because the is_endfile/1
test is not needed. However, most often one wants to do more
with the character rather than just test the eof, and only
then the differences are meaningful.
By the way, get0/1 does *not* exist in BSI, it uses get_char/1 instead,
and its argument is a character, i.e. a string of length 1.
This means that the type 'character' is inferred from
the type 'string' (and not the other way round like in C).
Does anybody out there know what advantages this can bring?
It is independent on the character <-> integer encoding,
but this only because explicit conversion predicates have
to be called all the time.
In his tutorial to the SLP '87 Richard has taken another
representation of a finite automaton which is more
appropriate:
s1 :-
get0(Char),
s1(Char).
s1(0'a) :-
s2.
s1(0'b) :-
s1.
s1(-1) :-
accept.
The difference is, that if one wants to perform some action
in some states, this must be done *before* reading the next character,
i.e. just at the beginning of s1/0. Such representation can
be more easily converted to the BSI's variant of get:
s1 :-
% do the corresponding action
( get0(Char) -> s1(Char)
;
accept
).
s1(0'a) :-
s2.
s1(0'b) :-
s1.
Note that the eof arc has to be merged into s1/0 in this way
since if we'd write it like
s1 :-
s1_action,
get0(Char),
!,
s1(Char).
s1 :-
accept.
then after an eof we would backtrack over s1_action and undo
what we've done.
I must say, none of the two seems to me satisfactory. Richard's
version is not portable due to the -1 as eof character. We can
improve this into
s1(X) :-
eof(X),
accept.
s1(0'a) :-
s2.
s1(0'b) :-
s1.
and hope that the compiler will unfold the eof/1 inside the
indexing mechanism, otherwise we have choice points even
if the code is deterministic.
The BSI version is much more arguable, though. Having to
wrap a disjunction (and a choice point) around the get0/1 call
suggests that for this application the BSI choice is not
the appropriate one. It is interesting to note, however, that
it could work even with nondeterministic automata, where the BSI's
failure was (I thought) more likely to cause problems.
For a Prolog system it is better to have get0/1 return
some *portable* eof (e.g the atom end_of_file, for get0/1
there can be no confusion with source items) instead of
some integer.
This, however, just shifts the problem up to read/1:
BSI objects that if it returns e.g. the atom end_of_file
then any occurrence of this atom in the source file
could not be distinguished from a real end of file.
In this case, a remedy would be the introduction of
a term with a local scope (e.g. valid
only in the module where read/1 and eof/1 are defined) and
using eof/1 instead of unifying the argument of read/1 with
the end_of_file term. Hence read/1 would return this term
on encountering the file end and eof/1 would check whether
its argument is this term.
--Micha
------------------------------
Date: 20 Mar 88 20:51:12 GMT
From: lagache@violet.Berkeley.EDU (Edouard Lagache)
Subject: Seeking opinions on BSI PROLOG standard proposal.
I spent a few hours carefully collecting all the
comments on the proposed BSI PROLOG standard that have been
posted to the PROLOG SIG. The result was a 160Kb file! The
reason for this exercise in tedium was my desire to write an
article on the pros and cons on this standard for the next
issue of the PROLOG Forum newsletter. However, for obvious
reasons, I am not particularly anxious to try to comb through
all them bytes of complex argumentation, and I am not
optimistic that I could do any of the participants justice.
Thus, I would like ask those persons who expressed some
substantial position on the new PROLOG standard, if they
might be interested in submitting to the PROLOG Forum
something equivalent to a short (1-3 page) position paper on
the standard.
Because we are such a new group, our editorial policies
are still in the process of coalescing, but at the moment I
would think that a very informal sort of piece of the sort
that you might post to the net would be very acceptable.
Should you have any interest and/or questions please
direct them to me, and I will do my best to answer them or if
necessary to rely them to our newsletter editor.
I am looking forward to a lot of interesting commentary!
-- Edouard Lagache
P.S. A minor detail, but anyone wishing to submit a text can simply
e-mail it to this account. If prefered, one could send an
PC or Mac compatible disk with the text in "flat ASCII" format to:
The PROLOG Forum
P.O. Box 3826
Redwood City, CA, 94064, USA.
------------------------------
Date: 21 Mar 88 16:40:44 GMT
From: eagle!icdoc!doc.ic.ac.uk!cdsm@ucbvax.Berkeley.EDU (Chris Moss)
Subject: BSI
Forwarded for Roger Scowen -- KRG0@gm.rl.ac.uk
RESPONSE TO COMMENTS FROM RICHARD O'KEEFE ON PROLOG STANDARDIZATION
GENERAL RESPONSE
Richard O'Keefe started by saying that he would respond to the
mailing from Chris Moss. In fact many comments refer
to a document (Prolog syntax, Draft 4.1) that
most news readers (and members of the ISO and BSI panels) will
not have seen.
This seems somewhat unfair on readers who will be unable to judge
whether draft, criticism, or rebuttal is justified.
First some general comments. The objective is to define an
International Standard for the programming language Prolog.
This means that standard conforming programs will run correctly
on standard conforming processors, neither more nor less.
It will not limit implementers from introducing new features and
facilities into their Prolog compilers.
Neither will it mean programmers cannot use such extensions; only
that if they do, their programs will not conform to the standard.
But a standard will permit people and companies to write applications
and libraries that will run on any conforming implementation
and thus give them a framework in which to work. In particular, such users
and their customers will not be restricted to a single implementation.
A standard will also give teachers, authors and students a common core
of useful Prolog.
Once a feature has been included in a standard, it is almost
impossible to remove. The committee remembers that Fortran has been
burdened with arithmetic if statements and computed goto statements.
In Prolog we hope to avoid such legacies if possible.
So some features of Edinburgh Prolog will not be in the standard
because although they fulfilled a need at one time, they are
not a sensible longterm solution.
Now some replies to specific criticism.
DIVERSITY OF EXISTING PROLOG SYSTEMS
Chris Moss has produced tests that give
different results on every system tested so far. Perhaps there
is rather more diversity than Richard O'Keefe realizes.
One objective has been to define a syntax where many existing
systems would not generally disagree on the meaning of
standard-conforming programs.
PROLOG CONTROL STRUCTURES AS SYNTAX
> (3) The attempt to describe Prolog control structures as *syntax*
> is fundamentally misdirected.
This is a matter of opinion. One reason for regarding Prolog control
structures as *syntax* is so that a person or program reading
a Prolog program can always recognize its overall structure.
NOTICE OF MEETINGS
Meetings are planned and advertised several months in advance,
for example, the following meetings are already planned:
BSI, London on Thursdays 2nd June, 1st Sept, 1st December 1988.
Any extra meetings to discuss the syntax will be on the previous
day (i.e. 1st June, etc); any meetings to discuss built-in predicates
will be a week later, i.e. 9th June, etc.
Everyone who wishes to attend is welcome. I admit that pressure of
work means that some papers are sent only a week before the meeting.
This is ample for British members of a British panel, but not for
Californian members.
But other papers will have been sent four or five weeks earlier.
All comments, whether they are received before or after a meeting,
are read and considered.
',' and '&' AS OPERATORS
It is not intended that it will be possible to declare ',' and '&'
as operators.
A MISTAKE IN COMMENTS
/** By L22, this is not a legal comment **/
Thank you. This will be a valid comment in standard Prolog despite
the error in this draft.
QUOTE OPERATORS USED AS OPERANDS
Richard O'Keefe realizes that the above example is intended to be
syntactically incorrect in the standard. When operators are
used as operands, there many problems of possible ambiguity.
A cure is still under discussion, but some problems are
avoided by the rule that "An operator used as an operand must be
bracketted".
AN INFIX CONS OPERATOR
We are still considering the problems posed by the multiple uses of '.',
i.e. as a decimal point, as an infix cons operator, and as a clause
terminator. At the same time we desire to make layout characters
unimportant in determining the meaning of a program.
Several possibilities have been suggested and are under consideration.
NEGATION
It is intended that Standard Prolog will not contain 'not' or '\+'.
Standard Prolog will not require systems to implement true
logical negation and it would be misleading to include an
operator or predicate that implies that they have done so.
Instead the way is left open for processors to implement a version
of 'not' as an extension and still remain standard conforming.
Standard Prolog will contain a built-in predicate
that implements 'negation by failure', i.e.
fail_if(G) :- call(G), !, fail.
fail_if(_).
A PARSER AS STANDARD
A program that resolves ambiguity implicitly is not acceptable as
defining a standard; there must be further definition.
One reason is that a program specifies too much. Some features need to
remain 'implementation dependent' because we must not specify
them, for example: the accuracy and largest values of floating point
numbers, or the integer value corresponding to a character.
Another reason is that it is harder to understand and find errors.
DISCLAIMER AND CONCLUSION
Never rely on working papers and draft standards. They are subject to
changes and review. All documents and working papers, however
confidently expressed, are also subject to review. There will be no
standard until the member bodies of ISO have approved it.
The next working drafts will incorporate changes arising from further
consideration and the comments received (including those from
Richard O'Keefe).
Many countries, but not at present USA, have national Prolog panels
coordinating their views on the emerging standard. I encourage all
Prolog implementers and users to participate in this effort in order that
the eventual standard is one that preserves the best of the past
and also provides development paths for the future.
-- Roger Scowen
-------------------------------
Date: 23 Mar 88 05:11:45 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: BSI syntax
Message-Id: <797@cresswell.quintus.UUCP>
References: <234@gould.doc.ic.ac.uk>
Sender: prolog-request@score.stanford.edu
To: prolog@score.stanford.edu
My postings were in fact a response to Chris Moss's mailing. They were
not confined to the content of that mailing, true. It seemed to me that
Chris Moss's mailing implied that the BSI syntax was in a satisfactory
state, and that it wasn't as difference from the de facto standard as
people feared. I set out to show that neither of those statements is
true, and I believe that I succeeded.
Many comments did refer to a document that most news readers won't have
seen. But then, most news readers won't have seen ***ANY*** of the BSI
documents. Am I then to say nothing? As for fairness to readers,
(a) I was quoting from the very latest document I had.
Surely it would be more unfair to quote from something I believed
to have been superseded?
(b) The "February 88" and "Feb 88" documents arrived in my mailbox here
in the same week. I had no way of telling who had or had not
received the document I was quoting. All I knew was that this was
the latest document available, sent to me by the author.
(c) In order to permit readers to judge for themselves whether my
criticisms were justified, I quoted extensively from the document.
I did not ask anyone to take it on faith that this or that was the
case: where the grimoire appeared to say something particularly
silly I exhibited the rules responsible. This is unfair?
> First some general comments. The objective is to define an
> International Standard for the programming language Prolog.
> This means that standard conforming programs will run correctly
> on standard conforming processors, neither more nor less.
> It will not limit implementers from introducing new features and
> facilities into their Prolog compilers.
>
> Neither will it mean programmers cannot use such extensions; only
> that if they do, their programs will not conform to the standard.
>
This is a little misleading. The general rule in other languages is
that implementors can add extensions, provided that such extensions
are either illegal or undefined in the standard. Thus a Pascal compiler
can provide alphabetic labels as an extension. But an implementor
should not provide an extension which alters the meaning of a program
which the standard would have ruled legal.
Let's apply this to the case of :- read(_). directives in a file which
is being consulted or compiled. Specifically, let's consider a file
which looks like
:- read(_).
p(a).
and has nothing else in it. Does this define p, or does it not? The
BSI grammar, in all versions, provides the syntax of entire files:
according to the grimoire this MUST mean exactly one directive followed
by exactly one clause. Since this is a defined and legal file, it would
be most improper for an implementor to give it any other meaning.
Therefore, reading out of a file being compiled or consulted is NOT
a permitted extension. (This wouldn't bother Quintus, but it is legal
in some other Prologs.)
Let's apply this to another case: functor/3. It has always been the
case in DEC-10 Prolog that functor(1, 1, 0). In at least one draft of
the BSI built-in predicates document, this has been required to raise
an error. (BSI Prolog includes an error handling facility; needless
to say it doesn't look like IF/Prolog's or M-Prolog's or ...) So a
BSI conforming program is entitled to rely on this error being raised,
and an implementor may NOT provide DEC-10 compatibility.
The ANSI C committee have found it necessary to explicitly indicate
which identifiers may be used by implementors. (The list includes
all identifiers starting with "_" or "str" and there are others I
can't remember right at the moment.) Why is this? Because the
programmer needs a guarantee that the identifiers he has chosen for
his code won't be in conflict with an implementation. For example,
(not)/1 is not defined in the BSI stuff, so Scowen says that an
implementation is free to define it. But if the implementation is
free to do so, then the programmer ISN'T. Since setof/3 is not in
the BSI Prolog language, a program which defines
setof(List, Set) :-
setof(List, [], Set).
setof([], Set, Set).
setof([Head|Tail], Set0, Set) :-
( member(Head, Set0) ->
setof(Tail, Set0, Set)
; /* not member(Head, Set0) */
setof(Tail, [Head|Set0], Set)
).
is a standard-conforming program. But a Prolog system which is exactly
BSI except for providing setof/3 as an extension is a conforming processor.
Will such a conforming program run correctly on such a conforming
processor? You must be joking. So, taken in their ordinary sense,
the claim that "standard conforming programs will run correctly on
standard conforming processors", while true of some standards, is NOT
true of the BSI work, unless "standard conforming processors" is
construed very strictly as meaning "providing NO additional built-in
predicates".
You will recall that Fortran 77 provides the EXTERNAL and INTRINSIC
statements precisely to cope with this problem, and that ANSI C
provides the reserved-to-implementors list and #undef precisely to
cope with this problem. BSI Prolog does have some reserved words,
but is ludicrously far from providing a solution to this problem.
> So some features of Edinburgh Prolog will not be in the standard
> because although they fulfilled a need at one time, they are
> not a sensible longterm solution.
Let's be realistic. There are languages on the horizon which are much
better approximations to logic programming than Prolog. (NU Prolog has
been around for a while.) There are lots of software engineering needs
which old Prolog completely failed to address, such as modules. (Last
I heard, the consensus of the BSI Modules subcommittee was that they
would probably never agree.) I think we ought to regard Prolog as a
stopgap; and that the goal of the standard should be to protect EXISTING
investments in Prolog. Frankly, advocates of BSI Prolog, with its
use of user-supplied atoms as stream names, are in no position to talk
about sensible solutions.
************************************************************************
** It would be most interesting to have an explicit list of the features
** of Edinburgh Prolog which fulfilled a need at one time and are now
** disliked by the committee, and a description of their replacements.
************************************************************************
> > (4) The basic structure of the BSI approach to syntax has been
> > to cut the Gordian Goose. That is, instead of regarding the
> > (actually rather low) diversity of Prolog syntax as an
> > opportunity to be solved by making the language more powerful
> > (e.g. having a table-driven tokeniser), it has been treated as
> > a problem to be solved by inventing a new, more restricted,
> > language.
>
> Well, yes and no. Chris Moss has produced tests that give
> different results on every system tested so far. Perhaps there
> is rather more diversity than Richard O'Keefe realizes.
> One objective has been to define a syntax where many existing
> systems would not generally disagree on the meaning of
> standard-conforming programs.
The amount of diversity one perceives depends on which "Prolog" systems
one decides to include in one's sample. My sample includes only systems
whose implementors _tried_ to be Edinburgh (or at least Clocksin &
Mellish) compatible. For example, AAIS Prolog is openly and frankly
not an Edinburgh-compatible system. We may (and should) look to it for
ideas, but we should not include it in a sample of "Edinburgh compatible"
Prologs. BIM Prolog has its own unique syntax; while we should perhaps
include the '-c' syntax of BIM Prolog in the sample, we should not
include BIM Prolog's native syntax. If we go by numbers, then Turbo
Prolog should determine the syntax of standard Prolog. If not by numbers,
by what? Simple justice suggests that the Prologs to look at are the
Prologs whose authors TRIED to be compatible with one another. Prudence
suggests the same sample.
But even if the diversity among the Prologs whose authors didn't suffer
from NIH-itis is much greater than I believe, that doesn't answer my
point. What I said was that the diversity should be regarded "as an
opportunity to be solved by making the language more powerful (e.g.
having a table-driven tokeniser)". [As an aside, this is no more than
Lisp and PopLog already have.] It turns out that it is quite easy to
write a tokeniser which can handle all of
ALS Prolog
Arity Prolog
BIM Prolog native syntax
C Prolog
DEC-10 Prolog
PopLog (nested comments)
Quintus Prolog
Stony Brook Prolog
and can almost handle ADA [ADA is no longer a trademark], simply by fiddling
with a table. AAIS took exactly this approach (though their tokeniser is
not as flexible as mine). I found it necessary to support several kinds
of quotes in my tokeniser:
ATMQT - the quoted thing is an atom (')
STRQT - the quoted thing is a string ($)
LISQT - the quoted thing is a list (")
CHRQT - the quoted thing is a character (`)
Suppose the standard were to adopt this approach, then they could rule,
if they wished, that the standard assignment was "->STRQT, with nothing
being assigned LISQT. That needn't prevent me reading my existing code:
I'd be able to change the table while reading my old files.
[The best approach seems to be to associate a read table with a stream;
naturally this is the approach PopLog takes.]
What I have in mind here is that a file would start with a directive
such as
:- use_syntax(dec10).
or :- use_syntax(standard).
or :- use_syntax(als).
Especially if the tokeniser were made available to user code (as it is
in the DEC-10 Prolog library, or built-in in NU Prolog), the result would
be a much more powerful language at very little cost to the implementor.
And conversion from old dialects to the BSI dialect would be enormously
simplified.
Do we need to come up with a "best possible" tokeniser for the standard?
Of course not.
Again, what are we to do about syntactic variations, such as the
treatment of operators? My answer, in 1984, was that the standard
should not specify read/1 and write/1, but should specify
standard_read/1
standard_write/1
and should allow users to redefine read/1 and write/1, but require
that the initial definitions be the standard one. consult and compile
should use read/1, not standard_read/1, so that someone who wanted to
read M-Prolog files into standard Prolog could do so by suitably
defining read/1.
Now, if you are a self-appointed standards committee member determined
to impose your vision of what is a "sensible longterm solution" on
every Prolog user whether they like it or not, this sort of approach
won't seem all that attractive. But if, like me, you think that the
people who matter in all this are the people who have paid money to
USE Prolog, and if, like me, you think that the fact that M-Prolog
is appalling is no reason to make life any harder for people with a
lot of data in M-Prolog format than we have to, you'll think that
letting people do
read(Term) :- magyar_read(Term).
is obviously the way to go. (It doesn't much matter how you install
your own code in the hook, the important thing is that there should be
a read-hook where you can install your own reader to be used by compile
and consult.)
> PROLOG CONTROL STRUCTURES AS SYNTAX
> > (3) The attempt to describe Prolog control structures as *syntax*
> > is fundamentally misdirected.
> This is a matter of opinion. One reason for regarding Prolog control
> structures as *syntax* is so that a person or program reading
> a Prolog program can always recognize its overall structure.
It is not a matter of opinion. Either I am right about this, or I am
wrong. There is a very important reason for my belief: Prolog is
simply not the sort of language for which this kind of thing can WORK.
Consider the difference between
foo(X, P, Q, L) :- bag(X, (P & Q), L).
^^^^^^^
and
de_morgan((P & Q), (R | S)) :- de_morgan(P, R), de_morgan(Q, S).
^^^^^^^
The first is code, and the treatment of it in the grimoire is appropriate.
(That is, it will be mapped to whatever "(and ?P ?Q)" would have been
mapped to in the BSI Lisp-like syntax.)
But the second is data, and the treatment of it in the grimoire is
NOT appropriate. It will be mapped to whatever "(and ?P ?Q)" would
have been mapped to in the BSI Lisp-like syntax, but it SHOULD be
mapped to whatever "[& ?P ?Q]" would be mapped to.
If we consider a slightly different example:
baz(X, P, L) :- bag(X, P, L).
^
and
de_morgan(not(P), R) :- de_morgan(P, R).
^
we find the opposite problem: the second is data and will be mapped to
whatever "?P" will be mapped to in the BSI Lisp-like syntax, but the
first is code, and should be mapped to whatever "(and ?P)" would be
mapped to, BUT IT WON'T BE.
The trouble is that the grimoire tries to guess whether something is
code or data by looking at its form, but that's the wrong place to
look: the place to look is the predicate being called. And the
trouble is that we can't build that information into the grammar,
because the programmer can define new predicates with code-like arguments.
Let me stress this:
the whole basis of the build-it-all-into-the-syntax approach
is the assumption that code is code and data are data and
never the twain shall meet.
This is true of Pascal. It is true of Fortran. It is almost true of C.
But it is utterly false of Lisp and Prolog. A grammar of this type does
not make SENSE for Prolog any more than it makes sense for Lisp.
I hereby wager US$100, payable once to Chris Moss, that if the next draft
of the grimoire attempts to maintain this rigid distinction between code
and data, I will be able to find inconsistencies like the ones above in
it. I don't think it's Chris Moss's fault: if anyone can find a way of
working around this basic mistake (not HIS mistake, by the way, this is
the kind of grammar the BSI committee have always wanted), I'm sure that
Chris Moss could. I make my wager *despite* my belief in Chris Moss's
competence, because I believe that it is _impossible_ for this approach
to work. (If I do not receive said draft by the end of this year, the
wager will expire.)
> ',' and '&' AS OPERATORS
> > Oddly enough, if one takes the grimoire literally, the user CAN
> > declare ',' and '&' as operators, and can use them in that form.
> > However, ',' and '&' cannot possibly have the same precedence as
> > "," or "&" in BSI Prolog, and it seems clear that (A ',' B) and
> > (A '&' B) must be different terms.
>
> It is not intended that it will be possible to declare ',' and '&'
> as operators.
>
There is nothing in the grimoire to say so, and it is a very odd restriction.
Intentions are beside the point: all that matters is what the documents
actually say. It *is* the intention that it should be possible to write
','(A,B) as a term, and it remains the case that ','(A,B) and '&'(A,B)
must be different terms, and if we take the grimoire literally, neither of
them can be the same as (A,B) or (A&B).
[Yes, I know about (P|Q) and (P;Q) in Dec-10 Prolog. I have always thought
and said that this was a mistake, and I think it is one of the very few
areas where a difference between the standard and existing practice might
be justifiable.
]
> QUOTE OPERATORS USED AS OPERANDS
> > compare(R, X, Y) :-
> > ( X @> Y -> R = >
> > ; X @< Y -> R = <
> > ; R = =
> > ).
>
> Richard O'Keefe realizes that the above example is intended to be
> syntactically incorrect in the standard. When operators are
> used as operands, there many problems of possible ambiguity.
> A cure is still under discussion, but some problems are
> avoided by the rule that "An operator used as an operand must be
> bracketted".
>
Well, it would be more accurate to say that I COMPLAIN that it is
intended to be syntactically correct in the standard.
There isn't any problem of possible ambiguity here whatsoever.
) :- ( :- must be infix
X @> Y @> must be infix
Y -> R -> must be infix
R = > = must be infix or suffix, has no suffix reading
= > ; > must be atom or prefix, has no prefix reading
> ; X ; must be infix
and so on
Now if = and > _both_ had a suffix reading, (R = >) would be ambiguous.
Since neither of them has, there is no ambiguity here at all.
The elimination of ambiguity is not a very good argument for breaking
existing UNAMBIGUOUS code!
> NEGATION
> > not Goal :- % "not" is not a built-in operator
> > ( ground(Goal) -> \+ Goal % neither is "\+".
> > ; signal_error(instantiation_fault(Goal,0))
> > ).
> It is intended that Standard Prolog will not contain 'not' or '\+'.
> Standard Prolog will not require systems to implement true
> logical negation and it would be misleading to include an
> operator or predicate that implies that they have done so.
> Instead the way is left open for processors to implement a version
> of 'not' as an extension and still remain standard conforming.
> Standard Prolog will contain a built-in predicate
> that implements 'negation by failure', i.e.
> fail_if(G) :- call(G), !, fail.
> fail_if(_).
My main point here was a semantic one. Most other control structures
are defined in the grammar. It seems odd that
( G -> fail ; true ) should be in the grammar, but that
fail_if(G) which is identical in effect, should not.
Because one of these forms is in the grammar and the other isn't, they
have different properties. For example,
( 1 -> fail ; true ) is syntactically illegal, but
fail_if(1) is syntactically legal.
There are other differences as well.
If BSI Prolog contains fail_if/1, then it WILL contain '\+', but with
a different name. Why not use an existing name for an existing
operation? Looks to me like nonhicinventusitis. \+ is a crossed-out
|-, meaning, obviously enough, "not provable".
> A program that resolves ambiguity implicitly is not acceptable as
> defining a standard; there must be further definition.
> One reason is that a program specifies too much. Some features need to
> remain 'implementation dependent' because we must not specify
> them, for example: the accuracy and largest values of floating point
> numbers, or the integer value corresponding to a character.
>
> Another reason is that it is harder to understand and find errors.
It is harder to understand and find errors in a program you can run
than in a never-used-anywhere-else formalism? Judging by the results,
this is the opposite of the truth.
What is the difference between the public-domain DEC-10 Prolog parser
and the BSI grimoire? Both are programs, in a formalism based on logic.
Neither is more explicit or less explicit than the other, and both are
of similar size. So what is the difference? The difference is that
the public-domain DEC-10 Prolog parser CAN be run, HAS been run, and
has had most of the mistakes knocked out of it by actual experience.
The BSI grimoire is in a new formalism, the definition of which is
provided in ***NO*** BSI document (so that I had to keep guessing what
things meant), and each of the three drafts I have seen was riddled
with errors from end to end. I haven't told you about all the problems
I found; there are nearly as many problems as rules!
The BSI Prolog group HAVE specified the integer value corresponding to
a character: they require the ISO 8859 character set. GREAT!
The DEC-10 public-domain ***parser*** does NOT specify the integer
value corresponding to a character (that's the tokeniser's job).
{The old tokeniser did have ASCII codes built in, but the current
version of the tokeniser uses 0'x syntax for the appropriate
constants to avoid that problem.}
If the BSI committee are so concerned to avoid character code problems,
how come they haven't got anything like 0'x or `x` (in a standard which
doesn't have to cope with existing code that uses ` as an atom, `x` is
a good notation for character code constants)?
The public-domain tokeniser doesn't specify anything more about floating
point numbers than what they look like, it relies on being provided with
a number_chars/2 predicate (which we want ANYWAY) do to the actual
conversion.
Note that the BSI grimoire says NOTHING about what happens if you write
a constant which exceeds the capacity of your implementation. Is the
program
p(1.2e3456).
a BSI-conforming program or not? Well, syntactically it is, but the
lexical rules say nothing about what it MEANS. For all that the
grimoire or any other BSI document I can recall says to the contrary,
a Prolog implementation which reads this as
p(0.0).
is conforming. This kind of thing is a real portability problem; it
exists with respect to integers too. Is 1000000000000000000 a legal
Prolog term? According to the grimoire, yes. What does it mean?
The grimoire doesn't say.
> DISCLAIMER AND CONCLUSION
> Never rely on working papers and draft standards. They are subject to
> changes and review. All documents and working papers, however
> confidently expressed, are also subject to review. There will be no
> standard until the member bodies of ISO have approved it.
But what ELSE is there to comment on?
> Many countries, but not at present USA, have national Prolog panels
> coordinating their views on the emerging standard. I encourage all
> Prolog implementers and users to participate in this effort in order that
> the eventual standard is one that preserves the best of the past
> and also provides development paths for the future.
>
> Roger Scowen, 11 March 1988
Sorry, but it's too late. Prolog implementors and users should have been
invited to contribute before the committee went on a four-year binge of
inventing their own language. I explicitly suggested some years ago that
the people at WISDOM should be invited to participate, and was told that
that was out of the question. I have put a lot of effort into writing
responses to the BSI stuff, and for all the feedback I've had I might as
well have been shouting into a vacuum. The BSI committee having been
resolute in their contempt for existing Prolog users (I have repeatedly
urged that they should explicitly adopt a principle of not breaking
existing code without strong necessity, as the ANSI C committee did, and
the last I heard was that they had explicitly rejected any such idea),
I cannot regard "preserves the best of the past" as anything but a sick
joke.
Look, if you want to preserve the best of the past, why have you
renamed findall/3 to bag/3? Why have you adopted ESI Prolog-2's
streams rather than Arity/Prolog's streams, despite having been
told about the problems? Could it be something to do with the
fact that the author of that part of the standard worked for ESI,
not for Arity? Why have you dropped nl/0 from the standard? Why
is there no notation for character constants such as PopLog provides?
Why is the error handling facility all new, rather than resembling
either IF/Prolog or M-Prolog?
I have tried, I really have tried, to arouse interest in the BSI work
here in the US. Do you know what has got in the way? As soon as I
show people any of the BSI documents (take the 'standardisation issues'
documents as an example) they say "what a pack of turkeys" and assure
me that there is nothing to worry about. I remain desperately worried
that there will be a BSI/ISO Prolog standard, and that it will be as
bad as the current drafts, and that it will do a great deal of damage.
What *really* worries me is that the people on the BSI committee don't
seem to realise how bad it is.
------------------------------
End of PROLOG Digest
********************