How to tell whether parentheses are necessary or not?

Question

I have written a parser in Haskell, which parses formulas in the form of string inputs and produces a Haskell data type defined by the BNF below.

formula ::=  true  
         |  false  
         |  var  
         |  formula & formula  
         |  ∀ var . formula
         |  (formula)

    var ::=  letter { letter | digit }*

Now I would like to create an instance of Show so that I can nicely print the formulas defined by my types (I don't want to use deriving (Show)). My question is: How do I define my function so that it can tell when parentheses are necessary? I don't want too many, nor too little parentheses.

For example, given the formula ∀ X . (X & Y) & (∀ Y . Y) & false which, when parsed, produces the data structure

And (And (Forall "X" (And (Var "X") (Var "Y"))) (Forall "Y" (Var "Y"))) False

we have

   Too little parentheses:    ∀ X . X & Y & ∀ Y . Y & false
   Too much parentheses:      (∀ X . (((X) & (Y)))) & (∀ Y . (Y)) & (false)
   Just right:                ∀ X . (X & Y) & (∀ Y . Y) & false

Is there a way to gauge how many parenthesis are necessary so that the semantics is never ambiguous? I appreciate any feedback.

See `showsPrec`, which `shows` something with a given operator `Prec`edence. — AJF, Dec 02 '18 at 22:20
@AJFarmar Can you recommend any tutorials on how to use `showsPrec`? The documentation I'm finding on it is quite minimal. — Luke Collins, Dec 02 '18 at 22:27
It's also a matter of taste. In my own preferred convention, `∀ X` has the lowest precedence, so that `∀ X . A & B` means `∀ X . (A & B)`, and not `(∀ X . A) & B`. (Sometimes the other precedence is used, instead.) Haskell also makes `\ x ->` to extend as to the right as possible. You have to choose the precedence. — chi, Dec 02 '18 at 23:09
@chi Normally I would agree with you, but given what I'm using this grammar for, it turns out that giving lower precedence to conjunction is more convenient. My question is not about choosing the precedence, but rather about how to actually implement the `show` function so that parentheses are printed minimally. — Luke Collins, Dec 02 '18 at 23:11
There's plenty of information on `showsPrec` already available. A quick google search reveals [this SO question](https://stackoverflow.com/questions/27471937/showsprec-and-operator-precedences), which I think is very helpful. — AJF, Dec 02 '18 at 23:20
Note that, in order to implement `showPrec`, you have to choose a precedence for your symbols. Essentially, you do have to choose which one between `∀ X . (A & B)` and `(∀ X . A) & B` can/should be written without parentheses. You want the latter, so the first will have parentheses -- that's OK. You need to assign a "precedence level" for your operators, and implement `showPrec` to add parentheses when you are in a context with a too high (I think) precedence. — chi, Dec 02 '18 at 23:24
I would suggest not using `Show`. `Show` is meant to output Haskell code, such that copy-pasting that code can (roughly) rebuild the original data. This should go into its own function. @chi's answer is still correct, and you can use all the `ShowS` stuff to implement your new function, but it should not be called `show`. — HTNW, Dec 03 '18 at 00:00

chi · Answer 1 · 2018-12-03T00:30:09.123

1

Untested pseudocode:

instance Show Formula where
   showsPrec _p True  = "True"
   showsPrec _p False = "False"
   showsPrec p (And f1 f2) = showParen (p > 5) $
      showsPrec 5 f1 . (" & " ++) . showsPrec 5 f2
   showsPrec p (Forall x f) = showParen (p > 8) $
      ("forall " ++ x ++) . showsPrec 8 f
   ...

(I should probably use showString instead of those ++ above. It should work anyway, I think.)

Above, the integer p represents the precedence of the context where we are showing the current formula. For example, if we are showing f inside f & ... then p will have the precedence level of &.

If we need to print a symbol in a context which has higher precedence, we need to add parentheses. E.g. if f is a | b we can't write a | b & ..., otherwise it is interpreted as a | (b & ...). We need to put parentheses around a | b. This is done by the showParen (p > ...).

When we recurse, we pass the precedence level of the symbol at hand to the subterms.

Above, I chose the precedence levels randomly. You need to adjust them to your tastes. You should also check that the levels you choose play along the standard libraries. E.g. printing Just someFormula should not generate things like Just a & b, but add parentheses.

edited Dec 03 '18 at 00:30

answered Dec 02 '18 at 23:37

chi

111,837
3
133
218

[I think you're fine without `showString` :P](https://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Show.html#showString). – HTNW Dec 02 '18 at 23:58
@HTNW It's only a matter of "style", indeed. :) – chi Dec 03 '18 at 00:29
I understand that you chose them randomly, but could you clarify what the integers 5 and 8 are actually doing here? Why not 1 and 2? – Luke Collins Dec 03 '18 at 21:19
1

@LukeCollins In principle, their value does not really matter, only their ordering does. However, one should try to choose the right ordering wrt the levels already used by the standard libraries. Otherwise, a formula will be printed correctly on its own, but incorrectly if e.g. inside a `Just` as the last example I wrote shows. In my experiments `Just x` gives level 11 to `x`, so to trigger parentheses. Instead `[x]` gives level 0 to `x` -- no parentheses needed here. Probably choosing your levels between 1 and 10 should be OK. – chi Dec 03 '18 at 22:19

How to tell whether parentheses are necessary or not?

1 Answers1