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",
>> }
>>
>
_______________________________________________
Haskell-prime mailing list
Haskell-prime@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-prime
