wiki:UnresolvedInfixExpressions

This page outlines a design for the "unresolved infix expressions" feature requested in #4430. Parts of this page are copied from the ticket.

Motivation

Consider writing a quasiquoter to parse haskell (for example, the parseHaskell quasiquoter mentioned in Part D of Simon's New directions for Template Haskell).

How is the quasiquoter supposed to handle infix expressions, such as

foo = [parseHaskell| 3 * 5 + 4 |]

In order to parse this expression properly, the quasiquoter needs to know the fixities of the operators mentioned, and this information is only available at the call site.

The solution proposed in this page is to extend the TH syntax datatypes to support "unresolved infix expressions" -- so that a quasiquoter can essentially say, "I have done as much parsing as possible, but you (GHC) will have to handle the fixities".

The API change

We add the following constructor (or similar) to template haskell's Exp datatype:

data Exp = 
     ...
     | UnresolvedInfixE [(Exp, Op)] Exp Section
     ...

and we add the following type synonym and datatype:

type Op = Exp
data Section = NoSection
             | LeftSection Exp
             | RightSection Exp

with the understanding that UnresolvedInfixE [("a","+"), ("b", "*")] "c" NoSection (here, and later, I write strings in place of syntax trees) denote the (unparenthesised) expression a + b * c with the expectation that GHC will apply the correct fixities when splicing (this will be explained in more detail later). The analogous interpretations for other values of the Section field are:

 UnresolvedInfixE [(e1,op1),(e2,op2),...,(en,opn)] efinal (LeftSection op)  ~~~ op e1 op1 e2 op2 ... en opn efinal
 UnresolvedInfixE [(e1,op1),(e2,op2),...,(en,opn)] efinal (RightSection op) ~~~ e1 op1 e2 op2 ... en opn efinal op

The meaning of splices containing UnresolvedInfixE

Suppose we have a splice containing an UnresolvedInfixE, such as

foo = $( ... (UnresolvedInfixE exprs expr) ... )

As with all splices, GHC will evaluate the TH syntax tree and then convert this to the type of syntax tree that GHC uses internally. When GHC comes across a constructor

UnresolvedInfixE [(e1,op1),(e2,op2),...,(en,opn)] efinal section

we use the following procedure:

  1. First, look up the operators op1,...,opn (and the operator in section if it exists) in the context where the UnresolvedInfixE occurs, and find out their fixities.
  2. Now look at the "expression"
        e1 op1 e2 op2 e3 op3 ... en opn efinal         (if section = NoSection)
     op e1 op1 e2 op2 e3 op3 ... en opn efinal         (if section = LeftSection op)
        e1 op1 e2 op2 e3 op3 ... en opn efinal op      (if section = RightSection op)
    
    and disambiguate it using the fixities of the op1,...,opn,op (following the Haskell rules for parsing unparenthesised infix expressions). The result will be a parenthesised (unambiguous) tree of infix expressions, for example any of the following:
     e1 op1 (e2 op2 (e3 op3 ... (en opn efinal)...)) -- if all operators were right-associative of equal precedence
     (...((e1 op1 e2) op2 e3) ... en) opn efinal     -- if all operators were left-associative of equal precedence
    
    This is the syntax tree that results.

Some special cases are worth pointing out.

  • The bold phrase, above, "in the context where the UnresolvedInfixE occurs" simply means that the operators are looked up by following all the lexical scoping rules, so that the correct fixities are found even in the presence of name shadowing. So, our hypothetical parseHaskell quasiquoter would behave as expected on
     [parseHaskell| let (++) = ... in x ++ y ++ z |]
    
    in the sense that the infix expression x ++ y ++ z is resolved using the fixity of the locally-defined (++) operator, rather than the fixity of (Prelude.++)
  • There is no special treatment of trees of UnresolvedInfixE. For example, the tree
     UnresolvedInfixE
      (UnresolvedInfixE e1 op1 e2)
        op2
      (UnresolveInfixE e3 op3 e4)
    
    will resolve to
     (e1 op1 e2) op2 (e3 op3 e4)
    
    no matter what the fixities of the operators are. In particular, this means that the tree just listed above behaves differently from the tree
     UnresolvedInfixE e1 op1 e2 op2 e3 op3 e4
    
    It is crucial that these two trees are treated differently, because the parseHaskell quasiquoter needs to distinguish between the following two expressions:
     [parseHaskell| (a + b) + (c + d) |]
     [parseHaskell| a + b + c + d     |]
    
    In the first expression, we do not want the compiler to reassociate the infix expression (because it is already parenthesised), but in the second expression, we do.
  • We have the following equivalences of syntax trees, as far as they are treated when splicing:
     InfixE (Just e1) op (Just e2)    <--->    UnresolvedInfixE [(e1,op)] e2 NoSection
     InfixE Nothing   op (Just e2)    <--->    UnresolvedInfixE []        e2 (LeftSection op)
     InfixE (Just e1) op Nothing      <--->    UnresolvedInfixE []        e1 (RightSection op)
     InfixE Nothing   op Nothing   <------------ this will be rejected when splicing.
     e                                <--->    UnresolvedInfixE []        e NoSection
    
    In view of the previous dot point, we see that there is no special treatment for trees of InfixE and UnresolvedInfixE constructors.
    These equivalences tell us that UnresolvedInfixE expressions are unambiguous if either:
    • the list has length 0; or
    • the list has length 1 and we have NoSection
    The redundancy introduced by these equivalences is discussed further down.
  • The following two syntax trees:
     UnresolvedInfixE [(e1,op1)] e2 (RightSection op)               say, generated by [parseHaskell| (2 + 3 +) |]
    
    and
     InfixE                                                             
       (Just $ UnresolvedInfixE [(e1,op1)] e2 NoSection)           say, generated by [parseHaskell| ((2 + 3) +) |]
       op                                                               
       Nothing                                                          
    
    are treated differently when splicing. If (+) is left-associative, then they will resolve the same way; if (+) is right-associative, then the first syntax tree will result in an error, whereas the second syntax tree will not.

    This demonstrates that it is necessary to include sectioning information in the UnresolvedInfixE constructor, as we do not want to silently convert illegal section expressions (such as (2 + 3 +) when (+) is right-associative) into legal, but different, section expressions (say ((2 + 3) +)).

Template Haskell Quotations and UnresolvedInfixE

If we have a Template Haskell quote containing infix expressions, for example

 foo = [| x + y * z |]

then how will these infix expressions be represented?

The important point is: the infix expressions will have already been resolved. (This is because GHC knows that (+) and (*) in the above example refer to the in-scope ones, so the fixities are known when the quote is constructed -- so we should certainly communicate this information.)

The precise representation of the (already-resolved) infix expressions will depend on whether the InfixE constructor will be removed, as discussed in the following section. At present, we can say the following:

  • if the InfixE constructor is not removed, then (already-resolved) infix expressions will be written in terms of the InfixE constructor, as is currently the case.
  • if the InfixE constructor is removed, then infix expressions will be written in terms of unambiguous UnresolvedInfixE expressions (see above for discussion of when UnresolvedInfixE expressions are unambiguous).

Redundancy; should InfixE be removed?

Because of the equivalences discussed earlier, we see that the InfixE constructor will be completely redundant after these changes. It is not clear to me what this means for design. The following are some options.

  • We could remove the InfixE constructor. Unfortunately, this means that every TH program which generates infix expressions would have to be changed.
  • We could modify the UnresolvedInfixE constructor to remove the ambiguity -- the idea being that UnresolvedInfixE is reserved for infix expressions which are truly ambiguous. This would involve requiring the list to be of length >=2 when we have NoSection, and length >=1 when we have LeftSection or RightSection. To do this the most obvious way ("unrolling" part of the list) unfortunately makes the constructors very large:
     data Exp = 
        ...
        | UnresolvedInfixE       [(Exp,Op)] Exp Op Exp Op Exp
        | UnresolvedLeftSection  Op Exp Op Exp [(Op,Exp)]    
        | UnresolvedRightSection [(Exp,Op)] Exp Op Exp Op
    
  • We could put up with the redundancy, and perhaps write a convertUnambiguousToInfixE :: Exp -> Exp which converts all unambiguous UnresolvedInfixEs to InfixEs.

Is there a better definition of UnresolvedInfixE?

The definition of UnresolvedInfixE I have given above is somewhat ugly, because it suggests an asymmetry which is not actually present. However, it manages to enforce the precise relationship that must hold between the number of operators and the number of operands -- which, for example, InfixE does not currently enforce.

Is there a better definition of this constructor?

Last modified 3 years ago Last modified on Nov 6, 2010 5:52:07 AM