kjell@terra.ucsc.edu (02/12/91)
(Sorry if this appeared before, I don't think my last posting made it.) Is there a document that describes the reader's behaviour when it sees an ambiguous term? Here's an example to show what I mean: :- op(300,fx,#). % prefix :- op(500,xf,#). % postfix :- op(400,fx,@). % prefix display(@ #). Will Prolog display @(#) or #(@), and why is one preferred over the other? --Kjell
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (02/13/91)
In article <12166@darkstar.ucsc.edu>, kjell@terra.ucsc.edu writes: > Is there a document that describes the reader's behaviour when it > sees an ambiguous term? Which Prolog? There *is* a document: the public-domain DEC-10 Prolog parser, published in 1984 (or was it 1983)? > :- op(300,fx,#). % prefix > :- op(500,xf,#). % postfix > :- op(400,fx,@). % prefix > display(@ #). > Will Prolog display @(#) or #(@), and why is one preferred over the other? In a Prolog system whose reader is based on the public-domain parser (the *point* of providing that was to help implementors tell the truth when they claimed "Edinburgh" compatibility), the answer must be #(@). THERE IS NOTHING AMBIGUOUS ABOUT THIS TERM: if a possible prefix operator is followed by - a right bracket of some sort , ) | ] } . - a possible infix operator of wider scope (bigger number) - or a possible postfix operator of wider scope (bigger number) then the possible prefix operator is read as an atom. (In the case of a following infix or postfix operator, this forces the operator reading.) -- Professional programming is paranoid programming
brady@swift.cs.tcd.ie (02/14/91)
In article <4764@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >> Will Prolog display @(#) or #(@), and why is one preferred over the other? > > In a Prolog system whose reader is based on the public-domain parser (the > *point* of providing that was to help implementors tell the truth when they > claimed "Edinburgh" compatibility), the answer must be #(@). > THERE IS NOTHING AMBIGUOUS ABOUT THIS TERM: > if a possible prefix operator is followed by > - a right bracket of some sort , ) | ] } . > - a possible infix operator of wider scope (bigger number) > - or a possible postfix operator of wider scope (bigger number) > then the possible prefix operator is read as an atom. > (In the case of a following infix or postfix operator, this forces > the operator reading.) Surely there _is_ an ambiguity here. If there wasn't, one wouldn't need to consult a programmed parser to resolve it! The DECsystem-10 User's Manual says that under certain circumstances a prefix operator can be taken as an atom. One can reasonably deduce that those circumstances are when there is no valid argument following the possible prefix operator - e.g. where there is a closing bracket, or a stop, or a term of a higher scope following. If that is the case, then, by taking the prefix interpretation of the #, and by turning it into an atom (because it has no following argument), then it seems legal for the prefix @ to take it (i.e. what is now the _atom_ # ) as its argument, yielding @(#). If seems that what Richard is saying is that this issue has been resolved de-facto (which is fine with me), but the ambiguity remains. I haven't thought of any 'collateral' consequences of this, but maybe there aren't any? Mike brady@cs.tcd.ie
bimbart@kulcs.cs.kuleuven.ac.be (Bart Demoen) (02/14/91)
I send the following on behalf of Roger Scowen. ------------------------------------------ Kjell (University of California, Santa Cruz) asks: > Is there a document that describes the reader's behaviour when it > sees an ambiguous term? Here's an example to show what I mean: > > :- op(300,fx,#). % prefix > :- op(500,xf,#). % postfix > :- op(400,fx,@). % prefix > > display(@ #). > > Will Prolog display @(#) or #(@), and why is one preferred over the other? Syntactic ambiguities in Prolog have been considered by the ISO Prolog standardization group. Different Prolog systems give different results, so there is no right answer. The latest draft (SC22 WG17 N70) forbids all ambiguous cases from occurring in a standard-conforming program. There are several restrictions, for example the case you have quoted is not allowed because the draft states (in 6.3.1.3): "an atom which is an operator shall not be the immediate operand of an operator". Roger Scowen, SC22 WG17 (Prolog) Convener, DITC/93, National Physical Laboratory, Teddington, Middlesex, England TW11 0LW 13 February 1991 Tel (Abroad): +44 81 943 6956 Fax (Abroad): +44 81 977 7091 Email: rss@seg.npl.co.uk Telex: 262344
kjell@saturn.ucsc.edu (Kjell Post) (02/15/91)
In article <4764@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <12166@darkstar.ucsc.edu>, kjell@terra.ucsc.edu writes: >> Is there a document that describes the reader's behaviour when it >> sees an ambiguous term? > >Which Prolog? There *is* a document: the public-domain DEC-10 Prolog >parser, published in 1984 (or was it 1983)? > >> :- op(300,fx,#). % prefix >> :- op(500,xf,#). % postfix >> :- op(400,fx,@). % prefix > >> display(@ #). > >> Will Prolog display @(#) or #(@), and why is one preferred over the other? > >In a Prolog system whose reader is based on the public-domain parser (the >*point* of providing that was to help implementors tell the truth when they >claimed "Edinburgh" compatibility), the answer must be #(@). >THERE IS NOTHING AMBIGUOUS ABOUT THIS TERM: > if a possible prefix operator is followed by > - a right bracket of some sort , ) | ] } . > - a possible infix operator of wider scope (bigger number) > - or a possible postfix operator of wider scope (bigger number) > then the possible prefix operator is read as an atom. > (In the case of a following infix or postfix operator, this forces > the operator reading.) Interesting. I hadn't seen that before and it certainly takes care of some problems. But what about this example? :- op(500,xfy,@). % infix :- op(600,xf,@). % postfix :- op(700,xf,#). % postfix display(a @ #). Quintus Prolog Release 2.2 (Sun-3, Unix 3.5) => @(a,#) SICStus 0.6 #18: Mon Oct 22 13:46:21 PDT 1990 => #(@(a)) ============================================================================== PS: Pnews didn't like my citation/comment-ratio so I included this picture: ***** ** ** ** ** * ** ******* * ** ** * ** *** * * __ __ * ** * / .\ /. \ * ** * \__/ \__/ * ** * . * * * * . * ** * * . * ** ** * * * * * **** * * * * ****** * * ** * ****** * * *** **** ****** * * ****** ** **** * * *** ** * *** ** ** * ********** * | * * | * *** --Kjell -- For athletes and programmers, ! Kjell E. Post a woman is the end of their career. ! CIS/CE ! University of California, Santa Cruz -- A.Wickberg ! Email: kjell@saturn.ucsc.edu
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (02/27/91)
In article <12388@darkstar.ucsc.edu>, kjell@saturn.ucsc.edu (Kjell Post) writes: > But what about this example? > :- op(500,xfy,@). % infix > :- op(600,xf,@). % postfix > :- op(700,xf,#). % postfix > display(a @ #). > Quintus Prolog Release 2.2 (Sun-3, Unix 3.5) => @(a,#) > SICStus 0.6 #18: Mon Oct 22 13:46:21 PDT 1990 => #(@(a)) It's amazing the problems you don't run into when you don't use postfix operators. I wish DHDW had never bothered to put them into DEC-10 Prolog. I think that #(@(a)) is the better answer here. I would point out that in SICStus 0.7, with these declarations, ?- writeq((a @) #). % #(@(a)) and ?- writeq(a @ (#)). % @(a,#) both produce the same output a@ # I think this brings out an EXTREMELY important point. A standard is at very much the same level as the "specification" of Prolog syntax we already have. We need a model implementation and a whole lot of nasty test cases like this that show that what the standard specifies can in fact be done. Thanks to Chris Moss for the syntax tests we do have; has someone got an additional collection of examples like this one? I would like to fix the public-domain reader. -- The purpose of advertising is to destroy the freedom of the market.
markh@csd4.csd.uwm.edu (Mark William Hopkins) (02/28/91)
In article <12388@darkstar.ucsc.edu>, kjell@saturn.ucsc.edu (Kjell Post) writes: > But what about this example? > :- op(500,xfy,@). % infix > :- op(600,xf,@). % postfix > :- op(700,xf,#). % postfix > display(a @ #). > Quintus Prolog Release 2.2 (Sun-3, Unix 3.5) => @(a,#) > SICStus 0.6 #18: Mon Oct 22 13:46:21 PDT 1990 => #(@(a)) In article <4834@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > >... I think that #(@(a)) is the better answer here. I agree. When you get to: a @ ..., the parser should immedicately interpret '@' as postfix, since the postfix operator has higher precedence and since it's in a infix/postfix context. That example's not quite as good as this Garden Path example: :- op(600,xfy,@). % infix :- op(500,xf,@). % postfix :- op(700,xf,#). % postfix display(a @ #). A good parser will try all possibilities either in breadth-first manner or by backtracking and report the first example as a precedence conflict, and actually accept the second as equivalent to: display(#(@(a)) (or maybe report this as a precedence conflict too). The problem is allowing operators to be used with different arities, which I personally find to be an extremely confusing and terrible style (so how could I blame a parser for getting confused too). >... We need a model implementation and a whole lot of >nasty test cases like this that show that what the standard specifies >can in fact be done.. Not really. A good mathematical analysis of the underlying syntax will reveal where all the critical points lie. For instance, applying a LALR(1) parser generator to the syntax for Prolog terms reveals these to be the critical points: (1) Op ( ... where Op can be a prefix operator. Is this to be interpreted as a prefix operator followed by a bracketed term or a prefix operator applied to an argument list in standard operator notation? Actually this is NOT a true ambiguity in most contexts, since either interpretation yields equivalent results. The only real problem ... wouldn't you guess ... is when your prefix operator has also been defined as an operator of different arity. Another place where it's a problem is in this context: prefix (Term) operator... where the second operator has smaller precedence than the first. This conflict is resolved by a certain convention concerning the placement of the bracket next to the prefix operator (at least in the dialects of Prolog I know of). (2) Op Op ... Any two adjacent operators (which is the operand?) (3) Op Term Op ... a prefix/infix operator, followed by a term, followed by an infix/postfix operator. This is mostly handled by operator precedences. (4) The comma in [...], f(...) contexts ... (5) High-precedence operators in similar contexts... these are handled by the precedence rules too.
micha@ecrc.de (Micha Meier) (03/04/91)
In article <4834@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >... We need a model implementation and a whole lot of >nasty test cases like this that show that what the standard specifies >can in fact be done. Thanks to Chris Moss for the syntax tests we do >have; has someone got an additional collection of examples like this one? >I would like to fix the public-domain reader. We have a complex syntax test suite made by Dominique Henry de Villeneuve some years ago. It takes a Prolog system and checks its behaviour on various aspects of the Prolog syntax. Since its output is quite lengthy, I have only made a comparison of the output of SICStus 0.7 and Quintus 2.0. The difference of the two output files was made with diff -DQUINTUS, so that the differences are highlighted with #ifdef's. 'error' means that an error was signalled but the execution went further, 'forbidden' means that the test could not be run because it aborts on this system. The operator tests list the operator definitions as current_op/3. No test can be complete, so any suggestions about items that could be added to the suite are welcome. --Micha ------------------------------------------------------------------------------- RESULTS OF TESTS ON OPERATORS 111- multiple definitions: prefix and infix #ifndef QUINTUS - a - b. =.. [-,-(a),b]-[] + a + b. =.. [+,+(a),b]-[] #else QUINTUS - a - b. =.. [-,-a,b]-[] + a + b. =.. [+,+a,b]-[] #endif QUINTUS #ifndef QUINTUS fy_yfx_8 fy_yfx_8 fy_yfx_8. =.. [fy_yfx_8,fy_yfx_8(fy_yfx_8)]-[current_op(500,fy,fy_yfx_8),current_op(500,yfx,fy_yfx_8)] #else QUINTUS fy_yfx_8 fy_yfx_8 fy_yfx_8. =.. error-[current_op(500,fy,fy_yfx_8),current_op(500,yfx,fy_yfx_8)] #endif QUINTUS #ifndef QUINTUS fy_yfx8 fy_yfx8 fy_yfx8 a. =.. [fy_yfx8,fy_yfx8(fy_yfx8,a)]-[current_op(500,fy,fy_yfx8),current_op(500,yfx,fy_yfx8)] fy_yfx8 fy_yfx8 fy_yfx8 fy_yfx8. =.. [fy_yfx8,fy_yfx8(fy_yfx8(fy_yfx8))]-[current_op(500,fy,fy_yfx8),current_op(500,yfx,fy_yfx8)] #else QUINTUS fy_yfx8 fy_yfx8 fy_yfx8 a. =.. error-[current_op(500,fy,fy_yfx8),current_op(500,yfx,fy_yfx8)] fy_yfx8 fy_yfx8 fy_yfx8 fy_yfx8. =.. error-[current_op(500,fy,fy_yfx8),current_op(500,yfx,fy_yfx8)] #endif QUINTUS 112- multiple definitions: postfix and infix #ifndef QUINTUS a yf_xfx_8 yf_xfx_8. =.. [yf_xfx_8,yf_xfx_8(a)]-[current_op(500,yf,yf_xfx_8),current_op(500,xfx,yf_xfx_8)] #else QUINTUS a yf_xfx_8 yf_xfx_8. =.. [yf_xfx_8,a,yf_xfx_8]-[current_op(500,yf,yf_xfx_8),current_op(500,xfx,yf_xfx_8)] #endif QUINTUS #ifndef QUINTUS a yf_yfx_9 yf_yfx_9 yf_yfx_9. =.. [yf_yfx_9,yf_yfx_9(a),yf_yfx_9]-[current_op(500,yf,yf_yfx_9),current_op(500,yfx,yf_yfx_9)] a yf_xfy_9 yf_xfy_9 yf_xfy_9. =.. [yf_xfy_9,yf_xfy_9(yf_xfy_9(a))]-[current_op(500,yf,yf_xfy_9),current_op(500,xfy,yf_xfy_9)] a yf_xfx_9 yf_xfx_9 yf_xfx_9. =.. [yf_xfx_9,yf_xfx_9(yf_xfx_9(a))]-[current_op(500,yf,yf_xfx_9),current_op(500,xfx,yf_xfx_9)] #else QUINTUS a yf_yfx_9 yf_yfx_9 yf_yfx_9. =.. error-[current_op(500,yf,yf_yfx_9),current_op(500,yfx,yf_yfx_9)] a yf_xfy_9 yf_xfy_9 yf_xfy_9. =.. [yf_xfy_9,a,yf_xfy_9(yf_xfy_9)]-[current_op(500,yf,yf_xfy_9),current_op(500,xfy,yf_xfy_9)] a yf_xfx_9 yf_xfx_9 yf_xfx_9. =.. error-[current_op(500,yf,yf_xfx_9),current_op(500,xfx,yf_xfx_9)] #endif QUINTUS RESULTS OF TESTS ON DOT 124- eof instead of fullstop? #ifndef QUINTUS aerror-[] #else QUINTUS aforbidden-[] #endif QUINTUS RESULTS OF TESTS ON INTEGERS 143- conversion char->integer #ifndef QUINTUS ~. = error-[] #else QUINTUS ~. = ~ -[] #endif QUINTUS RESULTS OF TESTS ON FLOATS 151- a float #ifndef QUINTUS float(1.2e). error-[] #else QUINTUS float(1.2e). yes-[] #endif QUINTUS #ifdef QUINTUS float(1.2e +6). no-[] #else QUINTUS float(1.2e +6). error-[] #endif QUINTUS RESULTS OF TESTS ON COMMENTS 180- comments inside Prolog terms #ifndef QUINTUS float(10/*comments*/.0). = error-[] #else QUINTUS float(10/*comments*/.0). = float(10.0)-[] #endif QUINTUS #ifndef QUINTUS float(10.5e/*comments*/+2). = error-[] #else QUINTUS float(10.5e/*comments*/+2). = float(10.5+2)-[] #endif QUINTUS 181- comments inside Prolog terms float(10%comments #ifndef QUINTUS .0). = error-[] #else QUINTUS .0). = float(10.0)-[] #endif QUINTUS float(10.5e%comments #ifndef QUINTUS +2). = error-[] #else QUINTUS +2). = float(10.5+2)-[] #endif QUINTUS 183- eof inside comments #ifdef QUINTUS %commentsa. = error-[] #else QUINTUS forbidden #endif QUINTUS #ifdef QUINTUS %a. = error-[] %a. = error-[] #else QUINTUS forbidden #endif QUINTUS 184- inside comments #ifdef QUINTUS /*/a. = error-[] #else QUINTUS forbidden #endif QUINTUS #ifdef QUINTUS /* /* /*a. = error-[] #else QUINTUS forbidden #endif QUINTUS RESULTS OF TESTS ON QUOTED ATOMS 203- null char in the escape sequence of quoted atoms #ifndef QUINTUS 'a\b'. = error-[] 'a\'. = error-[] '\b'. = error-[] #else QUINTUS 'a\b'. = a\ -[] 'a\'. = a\ -[] '\b'. = \ -[] #endif QUINTUS -- E-MAIL micha@ecrc.de MAIL Micha Meier ECRC, Arabellastr. 17 8000 Munich 81 Germany