2010-08-18

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 |> ff x
  • A rightwards application operator f %% xf x
  • A function composition operator f % g ≡ fun xf (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 xf (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.

8 comments:

bluestorm said...

> 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

No, it needs not. Just use the binding features of your host language !

let expr f g _loc =
<:expr< let f = $f$ and g = $g$ in fun x -> f (g x) >>

Notice that the use of the simultaneous "and" binding is essential here, as it ensures that the 'f' ident is not captured in $g$, and vice versa.
`let f, g = $f$, $g$ in ..` would also work.

I like that kind of tricks. They're fun, and to my eyes they're much cleaner that the "not formally safe but socially acceptable" kind-of-gensym hack. In fact, I have never encoutered a situation that could not be solved by such simple binding tricks. Is gensym really necessary ?



Regarding your global post : yes, pa_do is very powerful, but I'm not fond of the idea of operators that are rewrite rules instead of real functions (what if I want to write `List.fold_left (%) (fun x ->x ) func_list` ?), and I'm not sure it's a really good idea to depart from the standard OCaml associativity and precedence rules.

Besides the risk of conflict with ocaml native binary ops (what if you open a module that defines a (%%) identifier ?), I actually like the idea that associativity and precedence are determined from the operator characters, instead of an arbitrary and opaque "infixr 17" rule somewhere.

I agree that the precise OCaml rules are maybe not optimal ((|>) just doesn't work), but imho that's still a good way to go, and using pa_do to depart from it is discutable.

Matías Giovannini said...

The post by John Prevost I linked to made use of the same technique to avoid introducing a fresh variable. If the rewrite is as I've specified the variable "x" needs to be fresh; with the alternative rewrite you give no fresh variable is necessary.

Pa_infix doesn't seem to make operators accessible via the (%) syntax if it is not otherwise defined. The alternative is to define the operator (and export it via an interface), and use the default rewrite to <:expr< $lid:op$ $x$ $y$ >>, but I haven't tried that.

Regarding syntactic preference, old-guard OCaml practitioners seem to be content about the relatively spartan syntax (I'm firmly in that camp); newcomers, on the other hand, wail at the seemingly ad-hoc restrictions it has. À chacun selon son goût :-)

ChriS said...

Some quick comments.

1. Patches for improving the doc are gladly accepted!

2. pa_infix primary purpose is to change the priority or associativity of unary and binary operators. This only make sense when arguments are present. The optional rewrite rule must be seen as an added bonus—which allows e.g. |> to carry no cost in the above example. If you want (%) to work, you must bind it to a function.

I hardly use pa_infix myself but it was thought to be useful in situations like, say, “x $+$ y” where the standard precedence and associativity do not work well. We hoped to make this local but it does not seem possible with the current camlp4.

Matías Giovannini said...

@ChriS, so I've just played with essentially undocumented features of pa_do? I should make clear that the (%) operator is not an actual, real operator, but only a rewrite rule.

ChriS said...

No, it is not an undocumented feature (as you said, there is even an example using it) but it is not the primary purpose of pa_infix. Camlp4 requires to provide a “production”, so we allow to tweak it—and you can put that to interesting uses as you mentioned.

Also, about fresh variables:
- There is a function “new_lid” in Delimited_overloading ;
- I have been using them to create temporary variables to hold intermediate computations. For example, and expression “let x = Vec.(y + z + w)” may be transformed into “let x = let t = Vec.copy y in Vec.add_to t z; Vec.add_to t w; t” and it is important that “t” does not shadow “z” and “w”. Of course you could bind “z” and “w” first but I believe this would be slightly less efficient. (If it was not for efficiency, there would be no point in going all that trouble, just let each “+” create a new temporary vector.)
Another use is to create global variables to hold the result of constants. For example “Num.(2 + 2**345)” will put a single conversion of “2” to a Num at the beginning of the file which will be reused anytime a literal “2” has to be converted.

bluestorm said...

> Of course you could bind “z” and “w”
> first but I believe this would be
> slightly less efficient.

Have you tested it ? I seriously doubt it makes any difference.

http://www.c2.com/cgi/wiki?ProfileBeforeOptimizing

Matías Giovannini said...

@bluestorm, I might be talking out of my ass here, and I should really defer to Cristophe, but the point of his example is showing how it is necessary to generate fresh variables naming intermediate steps in a chain of mutations, where the parallel binding trick doesn't work. It is to be expected that, in general, accumulating into a mutable cell is faster than creating and discarding immutable intermediates.

ChriS said...

@bluestorm Here is an example:
--- a1.ml -----
let () =
let x = ref 0. in
for i = 1 to 100_000_000 do
x := 2. +. cos !x
done
--- a2.ml -----
let () =
let x = ref 0. in
for i = 1 to 100_000_000 do
let y = !x in x := 2. +. cos y
done
---------------
$ ocamlopt -o a1 -inline 3 a1.ml
$ ocamlopt -o a2 -inline 3 a2.ml
$ time ./a1
2.76user 0.00system 0:02.76elapsed 99%CPU (0avgtext+0avgdata 2752maxresident)k
0inputs+0outputs (0major+223minor)pagefaults 0swaps
$ time ./a2
2.91user 0.00system 0:02.92elapsed 99%CPU (0avgtext+0avgdata 3776maxresident)k
0inputs+0outputs (0major+287minor)pagefaults 0swaps

Note also that, for the sum, you will need to generate a sequence of bindings (since you do not know how many terms there are) so you will need a lowercase identifier generator — granted, you will not need to worry about conflicts.