Pretty print expression with as few parentheses as possible?

Question

My Question: What is the cleanest way to pretty print an expression without redundant parentheses?

---

I have the following representation of lambda expressions:

Term ::= Fun(String x, Term t)
      |  App(Term t1, Term t2)
      |  Var(String x)

By convention App is left associative, that is a b c is interpreted as (a b) c and function bodies stretch as far to the right as possible, that is, λ x. x y is interpreted as λ x. (x y).

I have a parser that does a good job, but now I want a pretty printer. Here's what I currently have (pseudo scala):

term match {
    case Fun(v, t) => "(λ %s.%s)".format(v, prettyPrint(t))
    case App(s, t) => "(%s %s)".format(prettyPrint(s), prettyPrint(t))
    case Var(v)    => v
}

The above printer always puts ( ) around expressions (except for atomic variables). Thus for Fun(x, App(Fun(y, x), y)) it produces

(λ x.((λ y.x) y))

I would like to have

λ x.(λ y.x) y

Answer 1

Here I'll use a simple grammar for infix expressions with the associativity and precedence defined by the following grammar whose operators are listed in ascending order of precedence

E -> E + T | E - T | T     left associative
T -> T * F | T / F | F     left associative
F -> G ^ F | G             right associative
G -> - G | ( E ) | NUM

Given an abstract syntax tree (AST) we convert the AST to a string with only the necessary parenthesis as described in the pseudocode below. We examine relative precedence and associativity as we recursively descend the tree to determine when parenthesis are necessary. Note that all decisions to wrap parentheses around an expression must be made in the parent node.

toParenString(AST) {
    if (AST.type == NUM)   // simple atomic type (no operator)
        return toString(AST)
    else if (AST.TYPE == UNARY_MINUS)  // prefix unary operator
        if (AST.arg.type != NUM AND 
           precedence(AST.op) > precedence(AST.arg.op))
              return "-(" + toParenString(AST.arg) + ")"
        else 
              return "-" + toParenString(AST.arg)
    else {  // binary operation
        var useLeftParen = 
             AST.leftarg.type != NUM AND
             (precedence(AST.op) > precedence(AST.leftarg.op) OR
              (precedence(AST.op) == precedence(AST.leftarg.op) AND
               isRightAssociative(AST.op)))

        var useRightParen = 
             AST.rightarg.type != NUM AND
             (precedence(AST.op) > precedence(AST.rightarg.op) OR
              (precedence(AST.op) == precedence(AST.rightarg.op) AND
               isLeftAssociative(AST.op)))

        var leftString;
        if (useLeftParen) {
           leftString = "(" + toParenString(AST.leftarg) + ")"
        else
           leftString = toParenString(AST.leftarg)

        var rightString;
        if (useRightParen) {
           rightString = "(" + toParenString(AST.rightarg) + ")"
        else
           rightString = toParenString(AST.rightarg)

        return leftString + AST.op + rightString;
    }
  }

Answer 2

Isn't it that you just have to check the types of the arguments of App?

I'm not sure how to write this in scala..

term match {
    case Fun(v: String, t: Term) => "λ %s.%s".format(v, prettyPrint(t))
    case App(s: Fun,    t: App)  => "(%s) (%s)".format(prettyPrint(s), prettyPrint(t))
    case App(s: Term,   t: App)  => "%s (%s)".format(prettyPrint(s), prettyPrint(t))
    case App(s: Fun,    t: Term) => "(%s) %s".format(prettyPrint(s), prettyPrint(t))
    case App(s: Term,   t: Term) => "%s %s".format(prettyPrint(s), prettyPrint(t))
    case Var(v: String)          => v
}