More OCaml Pretty-Printing

How to print expressions with binary operators using as few parentheses as possible. In this post, we avoid parentheses that are rendered unnecessary by precedence rules.

Consider the following type.

type op = Plus | Times
type expr = Op of op * expr list | I of int

And here is a value:

let v = Op (Plus, [I 3; Op (Times, [I 5; I 7; Op (Plus, [I 4; I 2])]); I 2])

If we don't care about how many parentheses are printed, we'd write

open Format

let op2s = function Plus -> '+' | Times -> '*'

let rec pp_list sep pp ppf = function
  | [] -> ()
  | [x] -> fprintf ppf "%a" pp x
  | x::xs -> fprintf ppf "%a%c%a" pp x sep (pp_list sep pp) xs

let rec pp ppf = function
  | Op (o, es) -> fprintf ppf "@[(%a)@]@," (pp_list (op2s o) pp) es
  | I x -> fprintf ppf "%d@," x

let _ = pp std_formatter v

The rule for precedence is simple: It's safe to strip parentheses in $(A \circ B) \bullet C$ if and only if $\circ$ has higher precedence than $\bullet$. It would be nice to isolate the code that decides whether parentheses are needed. We begin by removing grouping concerns from pp.

let pp r ppf = function
  | Op (o, es) -> pp_list (op2s o) r ppf es
  | I x -> fprintf ppf "%d" x

We can recover parentheses everywhere with a simple Y-like combinator.

let rec y1 f ppf x = fprintf ppf "@[(%a)@]@," (f (y1 f)) x
let pp1 = y1 pp
let _ = pp1 std_formatter v

Now pp1 does (almost) the same as the initial pp, the big difference being that we isolated the code that handles grouping. Because of this, implementing a policy based on operator precedences is simply a matter of defining another combinator.

let precedence = function 
  | Op (Plus, _::_::_) -> 1
  | Op (Times, _::_::_) -> 2
  | _ -> 0

let rec y2 up f ppf x =
  let down = precedence x in
  let lp, rp = 
    if down <= up && up <> 0 && down <> 0 then ("(", ")") else ("","") in
  fprintf ppf "@[%s%a%s@]@," lp (f (y2 down f)) x rp

let pp2 = y2 0 pp

let _ = pp2 std_formatter v