prefix minus and infix resolution

[Christian Maeder]

Simon Marlow schrieb:
> BTW, here's a related proposal made by Simon PJ earlier this year:
> 
> http://hackage.haskell.org/trac/haskell-prime/wiki/NegationBindsTightly
> 
> please consider merging the proposals, or at least clearly identifying
> the differences, if any.

Thanks for pointing this out.

The difference lies in:

 - 1 ^ 2

which is currently (and by my proposal) resolved to "- (1 ^ 2)" whereas
it would be resolved to "(-1) ^ 2" if negation binds tightly.

Christian

> 
> Cheers,
>     Simon
> 
> On 12/07/2010 08:40, Christian Maeder wrote:
>> Hi Simon and other fixity resolution friends,
>>
>> Fixity resolution starts from a sequence of expressions (lexp)
>> interspersed by operator symbols, where some expressions may be preceded
>> by unary minus signs.
>>
>> Between an operator and a following unary minus sign must be white space
>> for the haskell lexer (as in "x == -1").
>>
>> A binary minus is recognized (by the lexer), because it _follows_ an
>> expression (lexp) unlike an unary minus (that precedes).
>>
>> Conceptually fixity resolution can be divided into two steps:
>>
>> 1. resolve prefix applications of unary minus
>> 2. resolve infix applications
>>
>> There's no doubt how to resolve mere infix applications using
>> precedences and associativity (2. step):
>>
>> A term
>>    a `o` b `p` c
>> is uniquely resolve as:
>>   2.a) (a `o` b) `p` c
>>       if prec(o)>  prec(p)
>>       or prec(o) = prec(p) and both operator are left associative
>>   2.b) a `o` (b `p` c)
>>       if prec(p)>  prec(o)
>>       or prec(o) = prec(p) and both operator are right associative
>>   2.c) unresolved otherwise
>>
>> The prefix applications of unary minus is a bit unusual (compared to
>> other prefix applications) in that it binds weaker than multiplication:
>>
>>   "- 1 * 2" is to be resolved as "- (1 * 2)"
>>
>> This weak binding is irrelevant for multiplication but essential for
>> exponentiation, ie. "-x^2", and can make a difference for user defined
>> infix operators, that bind strongest by default!
>>
>> Resolution of prefix "-" (1. step) works as follows:
>>
>> Unary minus applications extend as far to the right as _infix_ operators
>> (no unary minus) have higher precedence than "+" or "-".
>>
>> A term like
>>    "- a * b ^ c<  - d ^ e * f"
>> is resolved as
>>    "- (a * b ^ c)<  - (d ^ e * f)"
>> or with more parens as
>>    "(- (a * b ^ c))<  (- (d ^ e * f))"
>> which further resolves by infix resolution (2. step) to
>>    "(- (a * (b ^ c)))<  (- ((d ^ e) * f))"
>>
>> In fact, this should finish fixity resolution, but the current haskell
>> state unnecessarily restricts resolution further:
>>
>> 3.a) "a * - b" is rejected, because "*" binds stronger than "-"
>> 3.b) "a + - b" is rejected, because "+" and "-" are not both right
>> associative
>>
>> although both terms can be uniquely resolved to "a * (- b)" "a + (- b)".
>>
>> In other words, the operator to the left of an unary minus can be
>> completely ignored for prefix minus resolution, simply because prefix
>> minus does not have a left argument (like the binary minus)!
>>
>> Without this restriction polynomials like
>>   "- a + - b * x + - c * - x ^ 2"
>> would uniquely resolve to
>>   "((- a) + (- (b * x))) + (- (c * (- (x ^ 2))))"
>>
>> I think hugs handles this correctly!
>>
>> Let us assume a user-defined (non- or) right-associative operator "#"
>> with the same precedence as "+" and "-" (infix[r] 6 #).
>>
>> 3.c) both "- a # b" and "a # - b" are rejected,
>>    because "#" is not left-associative (like "-").
>>
>> This unnecessary restriction rules out a (user-defined) polynomial like
>>   "- a # - b * x"
>> for two reason (namely the two unary minus signs).
>>
>> Because an operator like "#" is not predefined, this restriction does
>> not hurt as much as it does for "+" (and binary "-").
>>
>> The unrestricted fixity resolution (1. and 2. step only, without
>> restrictions 3.) can be further extended to allow multiple unary minus
>> prefix applications.
>>
>> infixexp ->   {-} lexp { op {-} lexp }
>>
>> White space is needed between "-" signs for lexing.
>> Extended cases of 3.a) and 3.b) would be legal:
>>    "a * - - b" resolves uniquely to "a * (- (- b))"
>>    "a + - - b" resolves uniquely to "a + (- (- b))"
>>
>> It is, however, worth to remark that two consecutive unary "-" sign
>> cannot be simply omitted:
>>    "a * - - b * c" resolves to "a * (- (- (b * c)))"
>>    whereas "a * b * c" resolves to "(a * b) * c"
>>
>> Even if double negation is the identity the grouping of factors has
>> changed.
>>
>> An (alternative) implementation of the unrestricted fixity resolution
>> can be found at:
>> http://hackage.haskell.org/trac/ghc/ticket/4180
>>
>> In comparison to the current restricted version the guard that checks
>> the left operator before the unary minus can be omitted. Also giving the
>> unary minus the same precedence and associativity than the binary minus
>> makes the algorithm more restrictive. The unary minus needs a higher
>> precedence than the binary "-" and a lower one than "*" or "/":
>>
>> Using http://darcs.haskell.org/haskell-prime it is enough to change:
>>
>> -type Prec   = Int
>> +type Prec   = Float
>>
>> -       = do guard (prec1<  6)
>> -            (r, rest')<- parseNeg (Op "-" 6 Leftfix) rest
>> +       = do
>> +            (r, rest')<- parseNeg (Op "-" 6.5 Leftfix) rest
>>
>> Cheers Christian
>>
>> Relevant literature is:
>>
>> @Article{Aasa95,
>>    author =       "Annika Aasa",
>>    title =        "Precedences in Specifications and Implementations of
>>                    Programming Languages",
>>    journal =      "Theoret.\ Comput.\ Sci.",
>>    year =         "1995",
>>    volume =       "142",
>>    pages =        "3--26",
>> }
>>
>