A Small jStar Demo

Old and New

This is an unusual post—imprecise, written late in the night, with no apparent purpose, and no apparent question. As I said, it is unusual. Not for the web, but for this blog.

All else being equal, and sometimes even when all things are not equal, some prefer old over new and others prefer new over old. Suppose you may choose between reusing a piece of code and writing it yourself. Suppose further that you have no objective reason to believe one option is better than the other. It is not clear that reusing old code will ensure you will have fewer bugs to fix in the future, since, obviously, you are an awesome programmer. (After all, you are reading this blog and recommending it to others. Nah. Forget that. I'm drunk. Really.) Back to the subject: You are awesome. I'd like to meet you. No. That was not the subject. Oh, right! So it's not clear that the old code you may reuse has very few bugs. There is also no obvious reason why you should be able to write more efficient code. That may be the case if your problem is a specialization of a general problem solved by the existing code. But that is not the case. Your problem is just as general as the existing library was designed to handle. But, wait! The library is there. Surely it must be quicker to just use it? No, it is not clear. Apparently you must coerce your build system through some hoops in order to accommodate the existing code. And you do need to write a "little" glue code. Just how little is "little" is hard to say. In short, as I said, you really have no idea of what would be better: to reuse or to write from scratch?

Yet, in spite of all I wrote above, I bet you know what is the right thing to do. You feel like telling me, like it is obvious. However, I am willing to bet that all your arguments have a counterfactual or philosophical flavor. Depending on who you are, you may feel like telling me that reusing code is the right thing to do, because it surely cannot be right for humans to keep reinventing wheels. We need to focus on the new stuff, right? "No. No. No." yells the other reader. It is much better to write the code yourself. In the long run, your purpose is to become a better programmer, and not writing the code yourself means giving up a great learning experience.

The point is that most people either prefer the old, or prefer the new—very few are indifferent. I happen to be in the former camp, but this is beside the point. I wonder if psychologists know what I am talking about.

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