Path: utzoo!mnetor!uunet!husc6!sri-unix!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: BSI syntax
Message-ID: <757@cresswell.quintus.UUCP>
Date: 11 Mar 88 08:03:32 GMT
References: <749@cresswell.quintus.UUCP>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 129
Summary: operator restrictions

With respect to operators, the current draft of the grimoire makes three
changes from DEC-10 Prolog.

(1) Programmers are not allowed to define operators at or above the level
    of comma.  This means that the type checker I posted to this group
    would be illegal, as it declares operators 'type' and 'pred' which
    resemble the 'mode' operator of DEC-10 Prolog.  It would also seem
    to have the effect of rendering any Prolog system which accepts
    DEC-10 Prolog 'mode' declarations non-conforming; the grimoire lists
    _all_ the operators it considers to be standard.  (The omission of
    the "existential quantifier" "^" and the "integer division"
    operator "//" from the table on page 5 are, I trust, unintentional.)

    The possibility of such operators does nothing to decrease the ease
    with which Prolog can be parsed.  I can't find the issue sheet where
    the reason for the change is given, but I _surmise_ that it is meant
    to make the language more comprehensible to people who try to read
    Prolog as if it were Pascal.  It's a relatively minor change to the
    language, so we might let it pass without comment.  But as Steve
    Hardy has pointed out:  read/1 is not exclusively used to read
    Prolog programs!  As an example, I[*] have a toy expert system shell
    (well, it's modelled on something which is sold as such) where you
    declare variables as e.g.

	company_type(year)/askable, company_type: cotype.
	cash_flow(year), working_capital(year): number.

    In order to make this work, I have to move ':' from its usual place
    in Quintus Prolog to just above ','.  It is not clear to me that the
    BSI committee are acting in my interests when they act to break this
    program.

    Is it reasonable to (ab)use read/1 like this?  Too right it is!
    That's what it's for!

    [*] Saying something about one of my programs won't please Bart Demoen.
	If he'll give me one of his programs, I'll be delighted to criticise
	it here.  I can't promise that _he'll_ be delighted, though!

(2) If an atom is declared as an operator, it is not allowed to be an
    operand of another operator.

    This is a breath-takingly elegant solution to the operator ambiguity
    problem.  If Prolog were still in the design phase, I'd be applauding
    this as a really good idea.  If this were the only difference between
    BSI Prolog and Edinburgh Prolog, I'd whinge a bit, but in a couple of
    years I'd be claiming that I'd thought of it first.

    The Edinburgh Prolog feature of requiring a prefix operator to be
    separated from a left parenthesis lest it be mistaken for a function
    symbol is retained.

(3) Further changes have been made in the interests of making the language
    parseable in C.  Specifically:
    o	"A right-binding operator binds more strongly than a left-binding
	 operator with the same declared priority number".
	I don't know what this means.  Perhaps it means that if
	    :- op(500, xfy, p), op(500, yfx, q).
	then
		a p b q c
	will be parsed as p(a, q(b,c)), which is just what Quintus Prolog
	does now.

    o	"One cannot have two operator definitions for the same symbol
	 current at the same time, with the exception of the combination
	 of the pair: infix and prefix.  This is to allow such uses as
	 unary minus, which are firmly embedded in mathematical notation".

    The main point of this message is that this last restriction is
    unnecessary.

    There was an article in SigPlan Notices, some time between 1978 and
    1982, which solved just this problem:  you have operators which can
    be prefix, infix, postfix, and you have operands.  How do you pick
    the right interpretation of the operators?

    Using A to stand for constants, bracketed terms, and other subterm(0)s,
    p to stand for a prefix operator, i for an infix operator, and s for a
    postfix operator (read "suffix"), a term must look like

	p* A {s* i p* A} s*

    That is, everything to the left of the left-most A must be a prefix
    operator, everything to the right-most A must be a postfix operator,
    and every string of operators between two As must be s* i p*.

    Note that this is not so easy in Edinburgh Prolog, because we haven't
    got those nice fixed As.  In practice, we almost always have, which is
    why backtracking is not a significant cost in actual Prolog-in-Prolog
    parsers, but we _might_ have an an arbitrarily long input term with no
    fixed atoms.  In BSI Prolog, because of change (2), this can't happen.

    So what ambiguity remains?  Suppose we have two As with n operators
    between them.  There is an n-fold ambiguity: any one of them could
    be the 'i', but once that is chosen, the others are fixed.

    What say we pick the left-most possible choice in such a group?
    This isn't necessarily the left-most possibly infix operator.
    If we have a postfix/infix operator followed by an infix-only
    one, it is the latter which is the left-most possible choice.
    If we want to be even more thorough, should there be multiple
    possible choices, we can use the fact that the infix operator
    must dominate the postfix operators preceding it and the prefix
    operators following it, and if there should be two or more choices
    remaining, we could report that as a syntax error.

    Why go to this sort of effort?  (Since Prolog terms are _much_
    shorter than Pascal programs, it is easy to over-estimate the effort
    required.)

    Well, there is a style of Prolog coding which uses operators
    extensively.  I refer, of course, to the "SIMPLE" syntax of LPA Prolog.
    In that notation, one normally treats all unary predicates as postfix
    operators, e.g.
	(john runs)
    and all binary predicates as infix operators, e.g.
	(john runs bsi)

    I don't happen to like this, but I don't see all that much point in
    forbidding it either, given that it has hitherto been permitted in
    Edinburgh Prolog.

    Note that in a term such as (john runs -> john isa runner)
    the only possible reading is    A    s  i    A   i      A
    because -> has no prefix reading.

    CONCLUSION:	it is possible to permit infix/postfix operators without
    losing deterministic parsing, thanks to the no-operators-as-operands
    restriction.