Proposal: PrefixMinusResolution

Compiler support

Summary

Resolve more prefix minus application unambiguously by:

1. Considering only operators to the right of prefix negation (as currently done by Hugs)

2. Leave prefix minus bind less tight than multiplication (as is currently done)

3. one of the following alternative formulations (the essence of this propoasl)

• Do not consider associativities for prefix minus resolution
• Let prefix minus bind a bit stronger than infix minus

Pro:

• Compatible with current state (fewer programs are rejected)
• fewer cryptic rejection messages involving prefix minus
• All prefix minus applications will be resolved

Cons:

• Does not explain why and how certain terms are resolved (if they are accepted)

Description

As described in NegationBindsTightly ghc rejects some terms that are accepted by Hugs and Helium and should not be rejected in general. However, making negation bind more tightly (as jhc does) is not the proposed solution here, because it would (in my eyes) wrongly resolve "- x ^ 2" to "(-1) ^ 2".

1. Only operators to the right of prefix negation need to be considered for resolution.

This condition ensures that "4 * -5" is not rejected (as ghc does).

1. Prefix minus should bind less tight than multiplication but …

2. .. (slightly) stronger than addition and subtraction.

The latter condition ensures that "- x # …" is resolved as "(- x) # …" for any operator # with lower precedence than multiplication.

"-4 * 5" will be resolved to "-(4 * 5)" as Hugs correctly does already. I don't know how Helium resolves this, but it does (usually) not matter for multiplication if it were resolved to "(-4) * 5".

However, Hugs rejects "-4 # 5" for a non-left-associative operator # with precedence 6, because it compares associativities for operators with the same precedence. Therefore prefix minus should have a (slightly) higher precedence than infix operators with the precedence of infix minus.

infix # 6
(#) = (-)
x7 = - 4 # 5

x7 are currently rejected by Hugs and ghc. Two solutions are possible. By accident nhc98 resolves this as "-(4 # 5), because # is not left-associative. I think associativity should only matter for two infix operators. Since "-" should just bind weaker than multiplication "(-4) # 5" should be the unique solution!

infixr # 6
(#) = (-)
x8 = - 4 # 5 # 6

x8 will be resolved as "(- 4) # (5 # 6)" like it would for any right-associative operator # with lower precedence, too. For any non-associative operator # "- 4 # 5 # 6" is rejected like "4 # 5 # 6", "-(4 # 5 # 6)" or "(-4) # 5 # 6" would be.

Surely, one can always disallow "confusing" resolutions, but if we reject "- 4 # 5", we can also reject "- 4 - 5" or "- 4 ^ 5". Associativity seems wrong to consider for the unary minus function. (But it is an option to simple use the way of Hugs or nhc98 for ghc, too.)

As a further option it is possible to support multiple prefix minus application. ("4 * - - 5" can be resolved in the same way as "4 * - 5" is).

References

For other examples see http://www.haskell.org/pipermail/haskell-prime/2010-July/003229.html (it also shows how easy an implementation is)

Mixfix analysis [Aasa95] usually only considers the top-level operators of argument terms. This backs my point 1. above: Do not look to the left of prefix minus, because there is no argument of prefix minus.

Also Isabelle ( http://isabelle.in.tum.de/) allows prefix operators to have lower precedence than infix operators. Other specification languages (like HasCASL) do so, too. For instance the logical prefix negation binds stronger than logical connectives but weaker than infix equality or other comparisons. (This does not apply to the "not" in Haskell, because "not" is a plain function, no operator).

Python's power operator binds more tightly than unary operators on its left, http://docs.python.org/reference/expressions.html, -1**2 results in -1.

Remarks

1. haskellch4.html#x10-820004.4.2 "4.4.2 Fixity Declarations" states:

"Any operator lacking a fixity declaration is assumed to be infixl 9"

This (surprisingly) makes "- a `f` b" resolve as "- (a `f` b)" for any f without fixity declaration (independent of this proposal). This contradicts NegationBindsTightly.

1. A pattern like "- 1 `f` b" must be rejected for `f` with higher precedence (than 6), because prefix minus is only allowed as part of a constant (see http://hackage.haskell.org/trac/ghc/ticket/4176)

2. As a compromise it is also an option to simple reject terms where prefix minus would not bind tightly (enough), which makes sense for "-a ^ b" and would force us to write "-(a ^ b)" or "(-a) ^ b" explicitly.

3. One would not want to reject "-a * b", no matter how it is resolved, but it would make a difference for `mod`, i.e. "- 1 `mod` 4"!

4. An incompatible fix for remark 1 would be to choose a different default precedence, i.e. 6. But since (in my eyes) mod is resolved the wrong way currently and we make incompatible changes anyway, it would make sense to increase the precedence of prefix minus to be just higher than multiplication (but still lower than exponentiation) and set the default precedence to 7 (like for multiplication). In case of doubt prefix application should bind stronger than infix application, but I do not want to make a proposal here, that would break compatibility.

Report Delta

In http://www.haskell.org/onlinereport/haskell2010/

remove "same precedence" stuff elsewhere (sections 3 and 3.4) and maybe add references to section 10.6 "Fixity Resolution".

remove: haskellch3.html#x8-220003 "Negation is the only prefix operator in Haskell; it has the same precedence as the infix - operator defined in the Prelude (see Section 4.4.2, Figure 4.1)."

remove: haskellch3.html#x8-280003.4 "Prefix negation has the same precedence as the infix operator - defined in the Prelude (see Table 4.1)"

extend: "… patterns are a subset of expressions so in what follows we consider only expressions for simplicity."

with: "Note, that prefix minus within patterns is only allowed for numeric constants that must not be followed by an infix (top-level) operator or constructor of higher precedence without brackets around the negated constant."

replace: "The function resolve takes a list in which the elements are expressions or operators, …"

with: "The function resolve takes a list in which the elements are expressions (lexp), negation or infix operators, …"

replace: "The handling of the prefix negation operator, -, complicates matters only slightly. Recall that prefix negation has the same fixity as infix negation: left-associative with precedence 6. The operator to the left of -, if there is one, must have precedence lower than 6 for the expression to be legal. The negation operator itself may left-associate with operators of the same fixity (e.g. +). So for example -a + b is legal and resolves as (-a) + b, but a + -b is illegal."

with: "The handling of the prefix negation operator, -, complicates matters only slightly. (Recall that) prefix negation has lower precedence than infix multiplication. So -a * b resolves as -(a * b) or more importantly -a ^ b as -(a ^ b). Generally, prefix negation extends as long to the right as there are consecutive infix operators with precedences at least as high as multiplication. The operator to the left of prefix -, if there is one, is irrelevant for resolution. So a + -b or a * -b are legal. Prefix negation binds tighter with infix operators to the right of lower precedence than multiplication. So for example -a + b is legal and resolves as (-a) + b."

(Use the algorithm from http://hackage.haskell.org/trac/ghc/ticket/4180) The description of the algorithm needs to be rewritten, too.

omit: "If we encounter a negation operator, and it is legal in this position (the operator to the left has precedence lower than 6), then we proceed in a similar way to case (3) above"

(negation is always legal, it's only a question how far it extends to the right)