prefix minus and infix resolution

[Christian Maeder]

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",
}