prefix minus and infix resolution
Simon Marlow
marlowsd at gmail.com
Tue Jul 13 08:58:42 EDT 2010
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.
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",
> }
>
More information about the Haskell-prime
mailing list