Path: utzoo!mnetor!uunet!husc6!sri-unix!quintus!ok From: ok@quintus.UUCP (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: BSI Proposal Message-ID: <786@cresswell.quintus.UUCP> Date: 18 Mar 88 12:32:21 GMT References: <229@gould.doc.ic.ac.uk> <771@cresswell.quintus.UUCP> <517@ecrcvax.UUCP> Organization: Quintus Computer Systems, Mountain View, CA Lines: 236 In article <517@ecrcvax.UUCP>, micha@ecrcvax.UUCP (Micha Meier) writes: > In article <771@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: > >As Chris Moss says, most languages since Fortran regard blanks as > >significant. Surely it is inconsistent to argue that > > "RED O" and "REDO" > >are different, and that is a Good Thing, but > > "red (O)" and "red(O)" > >being different is a Bad Thing? > I'm no fan of the allowed space between the functor and > the opening parenthesis, but this does not seem to me as > a good argument. In the usual languages blankspaces are > allowed between characters of different classes (in the POP > meaning of character classes), with some exceptions like > e.g. the floating point constants. From this point of view > a space between "red" and "(" seems rather natural, > to say that "red(" is one token seems to me at least arguable > (easy to implement, I admit). > Well, I have to admit that considered as an argument for distinguishing between "red (O)" and "red(O)", it's rather feeble. Plainly I need to take a course in effective communication, because the point I intended to make is that the BSI Junta are in no position to cast the first stone. I have a better example to support that position, which is that in one draft of the BSI grammar -1 is a negative number, but - 1 means -(1). I do not believe that this is intended to be a permanent feature of BSI Prolog. Which brings me to the next point: > Actually, we have implemented the BSI standard in our Sepia, > (it's probably one of the first implementations) Which version of BSI Prolog have you implemented? It hasn't really been fair of me to criticise the grimoire, because the "Feb 88" draft is dramatically different from the "February 88" draft. Early versions of BSI Prolog were essentially Sigma Prolog. Mid-range versions of the BSI Prolog builtins are pretty much ESI Prolog 2, including file position operations (seek/2, at/2) which don't make much sense except under MS-DOS or UNIX, and weren't all that brilliant if you wanted to support Kanji under UNIX. The latest stuff is a bit closer to Edinburgh Prolog. There was a real gem in 1987 where they decided that because they now had strings, they didn't need nl/0. (No smiley, this is true!) PS 176 lists nonvar/1 and nl/0 in section 1.15 "Predicates rejected for the standard." That was February 1987, mind you, which was only (:-) a little over two years since they started. [Pause for 10 minutes to locate more recent documentation.] According to PS/230 (dated November 1987): [1] at/2 and seek/2 are still there There is a clause/1 but no clause/2 [2] length/2 is "rejected" [3] nl/0 is "rejected" nonvar/1 is "rejected" [4] see/1, seeing/1, seen/0, tell/1, telling/1, told/0 are "rejected" setof/3 and bagof/3 are replaced by set/3 and bag/3 [5] sort/2 is present, but keysort/2 is missing without comment. [1] at(+Stream, -Position) tells you where you are. The text says that Position might be some sort of record. seek(+Stream, +Position) goes to a particular place. The text explicitly says that Position=300 must be accepted. It is required that at(S, 0) when S is at its beginning, and that seek(S, 0) will rewind S. (Why not, like C, admit that stream positions are system-dependent, and have a rewind/1? Idunno.) It is further required that there is a constant E such that end_of_file_mark(E) and at(S, E) iff S is at its end and that seek(S, E) will position the stream at the end. Logically, this entails that E==0 and that all streams must be empty. (The proof is obvious.) [2] length/2 being rejected doesn't mean you can't have it. What it *does* mean is that the present situation, where some Prologs can solve length(X, 3) and some can't, is considered quite acceptable by the committee. [3] The omission of nl/0 means that BSI Prolog has no portable way of ending an output record. The end-of-line character is 31 in DEC-10 Prolog, 10 in UNIX versions of Quintus Prolog, 13 in Xerox Quintus Prolog, and I not only haven't the foggiest notion what it is in the /370 port of Quintus Prolog, I don't need to know. In a record-oriented system, the very notion of an end-of-line character makes little sense, but nl/0 does! As an aside, as far as I am concerned one of the more serious defects of DEC-10 Prolog considered as a candidate for a standard is that it wouldn't cope well with record-oriented systems such as IBM's VM/CMS. The BSI group appears to have made no attempt to remedy this, and as evidenced by [1], they don't seem to realise that there is any problem. [4] Ok, the "see and tell" family was not the clearest, and streams such as C or Common Lisp (or even ADA) provide are a much better idea. But if you want to write portable code at the moment, you have to use them. Can they be implemented using the streams facility that BSI Prolog offers? As it happens, they CAN'T. They can be modelled faithfully using streams in Quintus Prolog or Arity/Prolog. Speaking from our experience at Quintus, getting the details right was surprisingly tricky. Not hard, there were just a lot of corners to watch out for. The BSI committee's choice means that vendors will continue to provide the "see and tell" family for backwards compatibility, but will continue to do it with variations. The streams provided in BSI Prolog are more like Fortran channels than like C streams: that is, a stream identifier is an atom that the programmer assigns. This means that it is impossible to write a library package which opens streams in such a way that it will never interfere with its user's streams. [5] The omission of keysort/2 is rather surprising. Recall that keysort/2 sorts a list of Key-Datum pairs stably, ignoring the Data. What does it do if one of the list elements has some other form? We've already seen one otherwise excellent Prolog use an unstable sort for keysort/2 (a "quick"-sort was used for speed, the irony is that it was SLOWER). This is the kind of thing a standard should address, but the BSI committee are content to leave this up to the vendor's imagination. Of course, it's clear why they've dropped keysort/2: BSI Prolog does not include bagof/3. What it has is findall/3. Only the name is different. The text of PS/230 says of sort/2 in section 15.3 NOTE: this predicate has a misleading name --HUH? and effect. --EH WHAT? It exists almost entirely because it is required in the implementation of set/3. --MAYBE. It seems unnecessary for the Prolog standard. How can a predicate have a misleading effect? sort/2 sorts, how is that a misleading name? (Mind you, it might have been better called sort_list/2.) This paragraph is, to my mind, conclusive proof that at least one person in the BSI committee has no idea of how to write efficient Prolog code. I keep finding that sort/2 makes the difference between an O(N*N) and an O(N*lgN) algorithm, and I cannot be indifferent to that. sort/2 and keysort/2 are of the utmost practical importance. But still, they provide @< (but NOT compare/3!), so one can implement sort/2 if one wishes. Is that a good reason for leaving it out? Well, if it is easy to implement, maybe it's ok to leave it out. But PS/230 provides good evidence that it isn't as easy as I thought. Here's their code: ?- mode(sort(+,?)). % NB! sort([], []). sort([X|T], [K|R]) :- smallest([X|T], K), remove(K, [X|T], Rest), sort(Rest, R). smallest([H|T], H) :- less_than_all(H, T), !. smallest([H|T], K) :- smallest(T, K). less_than_all(H, []). less_than_all(H, [N|L]) :- H @< N, less_than_all(H, L). remove(_, [], []). remove(K, [H|T], L) :- K == H, !, remove(K, T, L). remove(K, [H|T], [H|L]) :- remove(K, T, L). Now, the fact that this has cubic worst-case time is beside the point. It is only meant as a specification. But how can I have any confidence in the work of a standards committee whose official definition of sort/2 has the property that the query ?- sort([a,b,c], [c,b,a]). succeeds? The mode declaration explicitly permits such queries! It should come as no surprise that the official BSI definition of findall/3 (oops, sorry, that's a not-invented-here name, the real official BSI name is bag/3) has a similar bug. I've pointed out bugs in findall/3 enough times not to bore you with this one, it's an old friend. [6] There are built-in predicates atom/1, atomic/1, integer/1, real/1 &c. Fine, except that they don't do what other Prolog systems have them do. atom(X) must, in BSI Prolog, signal an error if X is a variable. Now this *would* have been a sensible idea back when Prolog was first being defined, but a change of this magnitude is quite out of place when you are standardising a language that already exists. My objection is not to there being built-in predicates with such an effect, but to using for them names that are already in use by most Prologs to mean something else. Compared with the description of the built-in predicates, the grimoire is a miracle of clarity and good sense. Mich Meier says > My global impression from BSI is, I'm afraid, close > to that of R.A.O'K, it is a new language, and very > difficult to implement. I've never really understood the grammar > and the 'Formal Specification of Prolog', though :-) > The Formal Specification is rather large. In fact PS/210 (the Formal Specification) says on page 15: "We need a language larger than Prolog standard." I have a formal definition which takes about 25 pages. It was dismissed by the BSI committee as "Pascal-like" (it uses a functional notation based loosely on ML) and "too hard to read". PS/120 is 122 pages, excluding indices. It is one of the sad ironies of life that the Formal Specification uses notational devices (such as the infix dot for cons) which the BSI committee has rejected from the language proper. A stylistic gripe about the Formal Specification is that the authors use one-letter variable names for the most part, and while there may perhaps be a naming convention which makes it all clear, I cannot figure one out and the text doesn't explain one. Let me try to make my position on the Formal Specification clear. Let its merits be as many and as important as they no doubt are. It will nevertheless be of no use to most people, including most implementors. The copy I have is physically heavier than a listing of C Prolog I have on the same weight of paper. For the purposes of a standard, we want a definition which can be used to assist in making implementations standard. This means that o it must be simple enough for most implementors to understand the whole specification o it must be usable as a comparison; that is, it must be possible to produce directly from the definition an implementation which is within perhaps a factor of 100 of a "real" implementation, so that non-trivial test cases can be run through it Let's face it, we want the bugs out of the specification BEFORE it is accepted as a standard.