What can pa_do for you?

(My puns are getting worse) A lot of things. Christophe Troestler pointed out that pa_do is a much more complete alternative to the new delimited overloading syntax in OCaml 3.12. In particular, it allows not only for the overloading of operators but of constants also, so that the following:

# Num.(3**(561-1) mod 561);;
- : Num.num = <num 375>

(561 = 3×11×17) works, with the simple (!) expedient of having a sane OCaml environment (findlib and omake are must-haves) and the inclusion of the relevant extensions. The delimited overloading expressions is the most visible, or ultimate, functionality of pa_do, but a key piece of the extension is the ability to define new operators much more flexibly than Standard OCaml syntax allows via pa_infix. The bad news is that the documentation is not entirely clear on how to proceed, so you need to dig through examples and list posts and experiment a bit to discover how to put it to productive use. One of the examples in the distribution is examples/pa_compos.ml, a good start for two reasons:

• It shows how to use the pa_infix API
• It shows how to leverage CamlP4 quotations to simplify (or optimize, or partially evaluate) generated code

I've extended the example a bit to create a syntax filter pa_compose.ml that defines three operators:

• A leftwards application operator x |> f ≡ f x
• A rightwards application operator f %% x ≡ f x
• A function composition operator f % g ≡ fun x → f (g x)

Note: Since <<, >>, $ and $$ are reserved by CamlP4 they are unavailable as operator names.

The key differences between pa_infix- and Standard Syntax-defined operators are three:

• They have specific precedence
• They have specific associativity
• They are rewrite rules, not regular functions

The |> and %% operators bind just higher than assignment :=, the former from left to right, the latter from right to left. The % operator binds higher than those, also from right to left. First I need to open the necessary modules:

open Camlp4.PreCast
open Pa_infix
module L = Level

The |> operator is just as in the example cited above, modulo some adjustments:

let () =
  let expr x y _loc = <:expr< $y$ $x$ >> in
  infix "|>" ~expr (L.binary (L.Higher L.assignment) ~assoc:L.LeftA)

The operator is assigned an arity, a precedence level and an associativity, and paired with a specific rewriting in the form of a CamlP4 quotation. This rewriting is made at the level of abstract syntax trees after the code is parsed, so there is no danger of it being syntactically incorrect. The %% operator is its mirror image:

let () =
  let expr x y _loc = <:expr< $x$ $y$ >> in
  infix "%%" ~expr (L.binary (L.Higher L.assignment) ~assoc:L.RightA)

The rewrite rules just make the operators disappear, leaving behind the semantics in the form of a direct application. The % operator is more involved, as it must create a variable to abstract the composition away. Since CamlP4 is not hygienic in the Scheme sense, this variable must be explicitly created fresh:

let gensym =
  Random.self_init();
  let prefix = Printf.sprintf "__pa_compose_%04x_" (Random.int 65536) in
  let count  = ref 0 in
  fun () -> prefix ^ string_of_int (incr count; !count)

For each rewriting of f % g as fun x → f (g x), the variable x must be fresh, otherwise it would capture in f % g % h:

let () =
  let expr f g _loc = let x = gensym () in <:expr< fun $lid:x$ -> $f$ ($g$ $lid:x$) >> in
  infix "%" ~expr (L.binary (L.Higher L.disjunction) ~assoc:L.RightA)

(The tag lid indicates an AST node containing an identifier). This is the entirety of the extension. It can be compiled with:

ocamlfind ocamlc -package pa_do -syntax camlp4o -ppopt q_MLast.cmo -c pa_compose.ml

to give pa_compose.cmo. With it, I'll try some examples, first using CamlP4 as a filter with the Standard Syntax pretty-printer:

camlp4 -parser o -parser op -printer o -I "$OCAMLLIB/site-lib/pa_do" pa_infix.cmo pa_compose.cmo compose.ml

The first examples are simple uses of the application operators. The code:

let test1 () = [1; 2; 3] |> List.map succ

gets transformed to:

let test1 () = List.map succ [ 1; 2; 3 ]

and the code:

let test2 () = List.map succ %% [1; 2; 3]

gets transformed to:

let test2 () = List.map succ [ 1; 2; 3 ]

Note that in both cases the operators disappear and the application is direct. The binding power of the first operator is shown as this code:

let test3 () =
  let x = ref 7 in
  x := !x |> succ

is transformed into this code:

let test3 () = let x = ref 7 in x := succ !x

and this code:

let test4 () =
  let x = ref 7 in
  x := succ %% !x

is transformed to this:

let test4 () = let x = ref 7 in x := succ !x

The rewriting is syntactically correct even in the presence of chained operators. This code:

let test5 () =
  [1; 2; 3] |> List.map succ |> List.fold_left (+) 0 |> succ

results in this transformation:

let test5 () = succ (List.fold_left ( + ) 0 (List.map succ [ 1; 2; 3 ]))

and this code:

let test6 () =
  succ %% List.fold_left (+) 0 %% List.map succ %% [1; 2; 3]

is transformed into:

let test6 () = succ (List.fold_left ( + ) 0 (List.map succ [ 1; 2; 3 ]))

The operators rewrite exactly to the same code, and they associate correctly into properly nested applications. The composition operator results in more complex expressions. The code:

let test7 () =
  succ % List.fold_left (+) 0 % List.map succ %% [1; 2; 3]

transforms into:

let test7 () =
  (fun __pa_compose_e2b2_2 ->
     succ
       ((fun __pa_compose_e2b2_1 ->
           List.fold_left ( + ) 0 (List.map succ __pa_compose_e2b2_1))
          __pa_compose_e2b2_2))
    [ 1; 2; 3 ]

which after β-reduction is identical to the code for test6 (of course % and %% are intimately related combinators, in that (%%) ≡ (%) id). Note that each abstraction has a freshly-generated, random-named variable. Similarly, the code:

let test8 () =
  [1; 2; 3] |> succ % List.fold_left (+) 0 % List.map succ

(not that it makes much sense) transforms into the same result, modulo α-conversion:

let test8 () =
  (fun __pa_compose_e2b2_4 ->
     succ
       ((fun __pa_compose_e2b2_3 ->
           List.fold_left ( + ) 0 (List.map succ __pa_compose_e2b2_3))
          __pa_compose_e2b2_4))
    [ 1; 2; 3 ]

To use the extension pa_compose to pre-process your source for compilation, it can be used like this:

ocamlfind ocamlc -package pa_do -syntax camlp4o -ppopt pa_infix.cmo -ppopt pa_compose.cmo -c compose.ml

It only remains building an OMakefile that compiles the extension both in bytecode and optimized assembly, packages it and installs it with findlib into the site library, so that it can be #require'd into the top-level.