Rewriting the Rules

The last article on pa_do sparked an interesting conversation with its author, Christophe Troestler, and reader bluestorm. It's true that pa_infix can establish optional rewrite rules for operators as a side-effect (or as an "added bonus" in the creator's words) of it installing new symbols with given arity, precedence and associativity. Given that rewrite rules are purely syntactical artifacts, there is no function associated with an operator unless explicitely defined. Of course, once defined they can be re-defined, and it is responsability of authors and users to keep both semantics (reduction and rewrite) in sync.

On the other hand, rewrite rules open the door to interesting optimizations before and beyond what the compiler sees and can perform. In the case of an extension for functional application and composition, the optimization is obvious: the identity function can be stripped when encountered in an applicative expression. Here is the syntax extension pa_compose.ml with these built-in optimizations (Edit: I've expanded a bit the check for the identity to catch references to the qualified module):

open Camlp4.PreCast
open Pa_do
open Pa_infix
module L = Level

let is_id = function
| <:ident< $uid:"Compose"$.$lid:"id"$ >>
| <:ident<                 $lid:"id"$ >> -> true
| _                                      -> false

let () =
  let expr x f _loc = match f with
  | <:expr< $id:f$ >> when is_id f -> x
  | f -> <:expr< $f$ $x$ >>
  in infix "|>" ~expr (L.binary (L.Higher L.assignment) ~assoc:L.LeftA)

let () =
  let expr f x _loc = match f with
  | <:expr< $id:f$ >> when is_id f -> x
  | f -> <:expr< $f$ $x$ >>
  in infix "%%" ~expr (L.binary (L.Higher L.assignment) ~assoc:L.RightA)

let () =
  let expr f g _loc = match f, g with
  | <:expr< $id:f$ >>, g when is_id f -> g
  | f, <:expr< $id:g$ >> when is_id g -> f
  | f, g ->
    let x = Delimited_overloading.new_lid () in
    <:expr< fun $lid:x$ -> $f$ ($g$ $lid:x$) >>
  in infix "%" ~expr (L.binary (L.Higher L.disjunction) ~assoc:L.RightA)

The great thing about CamlP4 is that it extends the syntax of OCaml to allow for writing matchings on the AST directly. The rules match explicitly on the lowercase identifier "id" and optimize away the application or the composition. In order to give executable semantics to the rewritten syntax, it is necessary to provide an implementation for the operators. Here is compose.ml:

external id : 'a -> 'a = "%identity"
let ( |> ) x f   = f x
let ( %% ) f x   = f x
let ( %  ) f g x = f (g x)

and here is its interface, compose.mli:

external id : 'a -> 'a = "%identity"
val ( |> )  : 'a -> ('a -> 'b) -> 'b
val ( %% )  : ('a -> 'b) -> 'a -> 'b
val ( %  )  : ('b -> 'c) -> ('a -> 'b) -> ('a -> 'c)

Both are utterly trivial, but necessary in order that the following:

let test9 () =
  [succ; succ; pred; id; succ] |> List.fold_left (%) id

works as intended. The following program, use.ml is a non-exhaustive test of the syntax extension:

(* Test of composition operators *)
open Compose

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

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

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

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

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

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

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

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

let test9 () =
  [succ; succ; pred; id; succ] |> List.fold_left (%) id

let test10 () =
  succ % Compose.id %% 10

let test11 () =
  id % succ %% 10

let test12 () =
  id % succ % id % pred %% 10

let test13 () =
  10 |> id

let test14 () =
  id %% 10

let test15 () =
  id % Compose.id % id %% 10

let () = Printf.printf "%d (should be 9)\n" (test9 () 7)

A quick-and-dirty Makefile to build the extension, its library, and the test program (provided you have findlib and pa_do installed, of course):

OCAMLC=    ocamlfind c   -w A
OCAMLOPT=  ocamlfind opt -w A -inline 10
PA_DO=     -package pa_do -syntax camlp4o

EXE=       .exe
PROG=      use$(EXE) use.opt$(EXE)
PACKAGE=   META compose.cmi compose.cmo compose.cmx pa_compose.cmo

ALL: $(PROG)

use$(EXE): compose.cmo use.cmo
    $(OCAMLC) -o $@ $^
use.opt$(EXE): compose.cmx use.cmx
    $(OCAMLOPT) -o $@ $^

pa_compose.cmo: pa_compose.ml
    $(OCAMLC) -c $(PA_DO) -ppopt q_MLast.cmo $<

pa_compose.cmx: pa_compose.ml
    $(OCAMLOPT) -c $(PA_DO) -ppopt q_MLast.cmo $<

use.cmo: use.ml
    $(OCAMLC) -c $(PA_DO) -ppopt pa_infix.cmo -ppopt pa_compose.cmo $<

use.cmx: use.ml
    $(OCAMLOPT) -c $(PA_DO) -ppopt pa_infix.cmo -ppopt pa_compose.cmo $<

use.pre.ml: pa_compose.cmo use.ml
    camlp4 -o $@ -parser o -parser op -printer o -I `ocamlfind -query pa_do` \
        pa_do.cmo pa_infix.cmo pa_compose.cmo use.ml

# Dependencies

compose.cmo: compose.cmi
compose.cmx: compose.cmi
pa_compose.cmo:
pa_compose.cmx:
use.cmo: pa_compose.cmo compose.cmi
use.cmx: pa_compose.cmo compose.cmi

# Phony targets

clean:
    rm -f *.cm* *.o *.obj *~

distclean: clean
    rm -f use.pre.ml $(PROG)

install: $(PACKAGE)
    ocamlfind install pa_compose $(PACKAGE)

uninstall:
    ocamlfind remove pa_compose

# Rules

.SUFFIXES: .cmo .cmi .cmx .ml .mli

.ml.cmo:
    $(OCAMLC) -c $<

.mli.cmi:
    $(OCAMLC) -c $<

.ml.cmx:
    $(OCAMLOPT) -c $<

(replace the spaces by tabs!) And a META file to package it as a ocamlfind extension:

name = "pa_compose"
version = "1.0"
description = "Rewrite rules for functional composition"
requires = "camlp4 pa_do pa_do.infix"
archive(syntax) = "@pa_do/pa_infix.cmo pa_compose.cmo"
archive(byte,toploop) = "@pa_do/pa_infix.cmo compose.cmo pa_compose.cmo"
archive(byte) = "compose.cmo"
archive(native) = "compose.cmx"

If you build the pre-processed example with make use.pre.ml, you'll see how the ids get rewritten away. Once built and installed, it can be directly used from the top-level:

$ ocaml
        Objective Caml version 3.12.0

Findlib has been successfully loaded. Additional directives:
  #require "package";;      to load a package
  #list;;                   to list the available packages
  #camlp4o;;                to load camlp4 (standard syntax)
  #camlp4r;;                to load camlp4 (revised syntax)
  #predicates "p,q,...";;   to set these predicates
  Topfind.reset();;         to force that packages will be reloaded
  #thread;;                 to enable threads

/usr/local/lib/ocaml/str.cma: loaded
/usr/local/lib/ocaml/dynlink.cma: loaded
# #require "pa_compose";;
C:/cygwin/usr/local/lib/ocaml/camlp4: added to search path
C:/cygwin/usr/local/lib/ocaml/site-lib/pa_do: added to search path
/usr/local/lib/ocaml/camlp4/camlp4o.cma: loaded
C:/cygwin/usr/local/lib/ocaml/site-lib/pa_do/pa_do.cmo: loaded
C:/cygwin/usr/local/lib/ocaml/site-lib/pa_do/pa_do_top.cma: loaded
C:/cygwin/usr/local/lib/ocaml/site-lib/pa_compose: added to search path
C:/cygwin/usr/local/lib/ocaml/site-lib/pa_do/pa_infix.cmo: loaded
C:/cygwin/usr/local/lib/ocaml/site-lib/pa_compose/compose.cmo: loaded
C:/cygwin/usr/local/lib/ocaml/site-lib/pa_compose/pa_compose.cmo: loaded
        Camlp4 Parsing version 3.12.0


# 3 |> succ |> succ |> id |> pred |> id |> succ ;;
- : int = 5

Of course, the functions themselves exist:

# open Compose ;;
# id ;;
- : 'a -> 'a = <fun>
# ( % ) ;;
- : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
# ( |> ) ;;
- : 'a -> ('a -> 'b) -> 'b = <fun>

Happy rewriting!

Polymorphic recursion with rank-2 polymorphism in OCaml 3.12

Using polymorphic recursion in OCaml just got easy and direct! With the new syntax, Okasaki's binary random-access lists translate to OCaml 3.12 practically verbatim, without the need for cumbersome encodings. You should refer to the book (Purely Functional Data Structures, p. 147) for comparison, but here's the implementation in its entirety:

type 'a seq = Nil | Zero of ('a * 'a) seq | One of 'a * ('a * 'a) seq

let nil = Nil

let is_empty = function Nil -> true | _ -> false

let rec cons : 'a . 'a -> 'a seq -> 'a seq =
  fun x l -> match l with
  | Nil         -> One (x, Nil)
  | Zero    ps  -> One (x, ps)
  | One (y, ps) -> Zero (cons (x, y) ps)

let rec uncons : 'a . 'a seq -> 'a * 'a seq = function
| Nil          -> failwith "uncons"
| One (x, Nil) -> x, Nil
| One (x, ps ) -> x, Zero ps
| Zero    ps   ->
  let (x, y), qs = uncons ps in
  x, One (y, qs)

let head l = let x, _  = uncons l in x
and tail l = let _, xs = uncons l in xs

let rec lookup : 'a . int -> 'a seq -> 'a =
  fun n l -> match l with
  | Nil                    -> failwith "lookup"
  | One (x, _ ) when n = 0 -> x
  | One (_, ps)            -> lookup (n - 1) (Zero ps)
  | Zero ps                ->
    let (x, y) = lookup (n / 2) ps in
    if n mod 2 = 0 then x else y

let update n e =
  let rec go : 'a . ('a -> 'a) -> int -> 'a seq -> 'a seq =
    fun f n l -> match l with
    | Nil                    -> failwith "update"
    | One (x, ps) when n = 0 -> One (f x, ps)
    | One (x, ps)            -> cons x (go f (n - 1) (Zero ps))
    | Zero ps                ->
      let g (x, y) = if n mod 2 = 0 then (f x, y) else (x, f y) in
      Zero (go g (n / 2) ps)
  in go (fun x -> e) n

The implementation given in the book is rather bare-bones, but it can be extended with some thought and by paying close attention to the techniques Okasaki uses. To begin with, a length function is a very simple O(log n) mapping from constructors to integers:

let rec length : 'a . 'a seq -> int
  = fun l -> match l with
  | Nil         -> 0
  | Zero ps     ->     2 * length ps
  | One (_, ps) -> 1 + 2 * length ps

It is also rather easy to write a map for binary random-access lists:

let rec map : 'a 'b . ('a -> 'b) -> 'a seq -> 'b seq =
  fun f l -> match l with
  | Nil          -> Nil
  | One (x,  ps) -> One (f x, map (fun (x, y) -> (f x, f y)) ps)
  | Zero ps      -> Zero     (map (fun (x, y) -> (f x, f y)) ps)

Note two things: first, that both parameters need to be generalized as both the argument and the return type vary from invocation to invocation, as shown by the Zero case. Second, that there is no need to use cons, as map preserves the shape of the list. With this as a warm-up, writing fold_right is analogous:

let rec fold_right : 'a 'b . ('a -> 'b -> 'b) -> 'a seq -> 'b -> 'b =
  fun f l e -> match l with
  | Nil          -> e
  | One (x, ps)  -> f x (fold_right (fun (x, y) z -> f x (f y z)) ps e)
  | Zero ps      ->      fold_right (fun (x, y) z -> f x (f y z)) ps e

Given a right fold, any catamorphism is a one-liner:

let append l = fold_right cons l

let of_list l = List.fold_right cons l nil
and to_list l = fold_right (fun x l -> x :: l) l []

Now, armed with fold_right, filling up a list library is easy; but taking advantage of the logarithmic nature of the representation requires thought. For instance, building a random-access list of size n can be done in logarithmic time with maximal sharing:

let repeat n x =
  let rec go : 'a . int -> 'a -> 'a seq = fun n x ->
     if n = 0 then Nil else
  if n = 1 then One (x, Nil) else
     let t = go (n / 2) (x, x) in
     if n mod 2 = 0 then Zero t else One (x, t)
  in
  if n < 0 then failwith "repeat" else go n x

By analogy with binary adding, there is also a fast O(log n) merge:

let rec merge : 'a . 'a seq -> 'a seq -> 'a seq =
  fun l r -> match l, r with
  | Nil        ,         ps
  |         ps , Nil         -> ps
  | Zero    ps , Zero    qs  -> Zero (merge ps qs)
  | Zero    ps , One (x, qs)
  | One (x, ps), Zero    qs  -> One (x, merge ps qs)
  | One (x, ps), One (y, qs) -> Zero (cons (x, y) (merge ps qs))

It walks both lists, "adding" the "bits" at the head. The only complication is the case where both lists are heded by two Ones, which requires rippling the carry with a call to cons. An alternative is to explicitly keep track of the carry, but that doubles the number of branches. This merge operation does not preserve the order of the elements on both lists. It can be used, however, as the basis for a very fast nondeterminism monad:

let return x = One (x, Nil)
let join mm  = fold_right merge mm Nil
let bind f m = join (map f m)

let mzero = Nil
let mplus = merge

The rank-2 extension to the typing algorithm does not extend to signatures, as in Haskell. It only has effect on the typing of the function body, by keeping the type parameter fresh during unification, as the signature of the module shows:

type 'a seq = Nil | Zero of ('a * 'a) seq | One of 'a * ('a * 'a) seq
val nil : 'a seq
val is_empty : 'a seq -> bool
val cons : 'a -> 'a seq -> 'a seq
val uncons : 'a seq -> 'a * 'a seq
val head : 'a seq -> 'a
val tail : 'a seq -> 'a seq
val lookup : int -> 'a seq -> 'a
val update : int -> 'a -> 'a seq -> 'a seq
val length : 'a seq -> int
val map : ('a -> 'b) -> 'a seq -> 'b seq
val fold_right : ('a -> 'b -> 'b) -> 'a seq -> 'b -> 'b
val append : 'a seq -> 'a seq -> 'a seq
val of_list : 'a list -> 'a seq
val to_list : 'a seq -> 'a list
val repeat : int -> 'a -> 'a seq
val merge : 'a seq -> 'a seq -> 'a seq
val return : 'a -> 'a seq
val join : 'a seq seq -> 'a seq
val bind : ('a -> 'b seq) -> 'a seq -> 'b seq
val mzero : 'a seq
val mplus : 'a seq -> 'a seq -> 'a seq

To use rank-2 types in interfaces it is still necessary to encode them via records or objects.

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.

Compiling OMake 0.9.8.5 with OCaml 3.12/MinGW under Cygwin

Success! Since OMake doesn't really have a notion of a build environment, just one of platform (UNIX or Win32), compiling the latest release (0.9.8.5-3) from sources requires a number of modifications to the makefiles. Furthermore, OCaml has incorporated a number of warnings that make necessary adjusting some command-line parameters.

Note: These steps are specifically for the MinGW port of OCaml. If you're trying to build with OCaml/Cygwin, you'd want to keep most of the settings in the makefiles intact, except for adjusting the OCaml warnings. YMMV.

Here are the steps I followed for a clean build from sources:

1. Make sure that your Cygwin environment is sane. In particular, prune from your $PATH variable all entries with spaces, make sure that $OCAMLLIB is properly set and eliminate the $OMAKELIB variable if present. Also, using Cygwin under Windows Vista or Windows 7 is fraught with privilege peril; set your $TMP variable to Cygwin's /tmp directory
2. Download and unpack omake-0.9.8.5-3.tar.gz to Cygwin's root /
3. Apply the source patches detailed here:
   1. omake_exec.ml.patch:

      --- a/src/exec/omake_exec.ml    2006-12-08 23:52:01.000000000 +0100
      +++ b/src/exec/omake_exec.ml    2009-10-30 23:45:49.688006630 +0100
      @@ -46,7 +46,7 @@
       open Omake_options
       open Omake_command_type
      
      -external sync : unit -> unit = "caml_sync"
      +(* external sync : unit -> unit = "caml_sync" *)
      
       module Exec =
       struct
      

   2. lm_printf.c.patch:

      --- a/src/libmojave-external/cutil/lm_printf.c  2007-07-15 19:55:23.000000000 +0200
      +++ b/src/libmojave-external/cutil/lm_printf.c  2009-10-30 23:45:26.600007718 +0100
      @@ -142,12 +142,12 @@
       #endif
           if(code < 0) {
               if(bufp != buffer)
      -            free(buffer);
      +            free(bufp);
               failwith("ml_print_string");
           }
           v_result = copy_string(bufp);
           if(bufp != buffer)
      -        free(buffer);
      +        free(bufp);
           return v_result;
       }
      
      @@ -190,12 +190,12 @@
       #endif
           if(code < 0) {
               if(bufp != buffer)
      -            free(buffer);
      +            free(bufp);
               failwith("ml_print_string");
           }
           v_result = copy_string(bufp);
           if(bufp != buffer)
      -        free(buffer);
      +        free(bufp);
           return v_result;
       }
      

4. Patch the Makefile with the following Makefile.patch:

   --- Makefile.orig 2007-05-21 13:48:00.000000000 -0300
   +++ Makefile 2010-08-16 13:23:37.352895400 -0300
   @@ -18,18 +18,18 @@
     @exit 1
    
    bootstrap: boot/Makefile
   - @cd boot; $(MAKE) Makefile.dep; $(MAKE) omake
   - @ln -sf boot/omake omake-boot
   + @cd boot; $(MAKE) Makefile.dep; $(MAKE) omake.exe
   + @cp boot/omake.exe omake-boot.exe
    
    boot/Makefile: src/Makefile
     mkdir -p boot
     @touch boot/Makefile.dep
     @sleep 1
   - ln -sf ../src/Makefile boot/Makefile
   + cp src/Makefile boot/Makefile
    
    all: bootstrap
     touch .config
   - OMAKEFLAGS= OMAKEPATH=lib ./omake-boot --dotomake .omake --force-dotomake -j2 main
   + OMAKEFLAGS= OMAKEPATH=lib ./omake-boot --dotomake .omake --force-dotomake -j2 main src/main/osh.exe
     OMAKEFLAGS= OMAKEPATH=lib src/main/omake --dotomake .omake --force-dotomake -j2 all
    
    install: all
   

   These modifications account for MinGW applications's inability to read from symbolic links, and the need to use .exe as the executable files's extension.

5. Patch src/Makefile with the following src_Makefile.patch:

   --- src/Makefile.orig 2007-06-27 20:59:16.000000000 -0300
   +++ src/Makefile 2010-08-16 13:26:35.342346000 -0300
   @@ -7,32 +7,32 @@
    #
    # System config
    #
   -LN = ln -sf
   +LN = cp
    RM = rm -f
    DOT = ./
    slash = /
    
   -win32 = unix
   -system = null
   +win32 = win32
   +system = system
    
    #
    # C configuration
    #
   -CC = cc
   -CFLAGS =
   +CC = gcc
   +CFLAGS = -mno-cygwin -I"$(OCAMLLIB)" -DWIN32 -DFAM_ENABLED -DFAM_PSEUDO
    AR = ar cq
    AROUT =
    EXT_OBJ = .o
    EXT_LIB = .a
   -EXE =
   +EXE = .exe
    
   -OCAMLFLAGS =
   -THREADSLIB =
   +OCAMLFLAGS = -thread
   +THREADSLIB = threads.cma
    
    .SUFFIXES: .mll .mly .mli .ml .c .cmi .cmo .cma .o
    
    .c.o:
   - $(CC) $(CFLAGS) -I"`ocamlc -where`" -c $*.c
   + $(CC) $(CFLAGS) -c $*.c
    
    
    #
   

   Again, this accounts for the fact that MinGW applications under Cygwin are Windows applications with UNIX syntax.

6. Patch OMakeroot with the following OMakeroot.patch:

   --- OMakeroot.orig 2010-08-16 13:31:07.517242100 -0300
   +++ OMakeroot 2010-08-16 13:31:13.423692900 -0300
   @@ -14,7 +14,13 @@
    #
    # Include the standard configuration
    #
   -include build/C
   +OSTYPE = Cygwin
   +open build/Common
   +EXT_LIB = .a
   +EXT_OBJ = .o
   +EXE = .exe
   +open build/C
   +CC = gcc -mno-cygwin
    include build/OCaml
    include build/LaTeX
    
   @@ -29,6 +35,9 @@
    #
    include configure/Configure
    
   +OSTYPE = Win32
   +TOOLCHAIN = MinGW
   +
    #
    # Include the OMakefile
    #
   

   The rationale behind these modifications can be found in this message. In short, it tricks the initial configuration into thinking it's a UNIX platform, and then reverts to the Win32 port, setting a variable for OMakefile.

7. Patch OMakefile with the following OMakefile.patch:

   --- OMakefile.orig 2010-08-16 13:29:07.788616600 -0300
   +++ OMakefile 2010-08-16 13:29:13.828708200 -0300
   @@ -15,7 +15,14 @@
        #
        # Extra options for the C compiler
        #
   -    CFLAGS += /MT /DWIN32 /W4 /WX
   +    if $(equal $(TOOLCHAIN), MinGW)
   +        CFLAGS += -DWIN32
   +        FAM_CFLAGS = -DFAM_ENABLED -DFAM_PSEUDO
   +        export
   +
   +    else
   +        CFLAGS += /MT /DWIN32 /W4 /WX
   +        export
    
        #
        # Don't build man pages
   @@ -57,7 +64,7 @@
    #
    # OCaml options
    #
   -OCAMLFLAGS[] += -w Ae$(if $(OCAML_ACCEPTS_Z_WARNING), z)
   +OCAMLFLAGS[] += -w Ae$(if $(OCAML_ACCEPTS_Z_WARNING), z)-9-27..29
    if $(THREADS_ENABLED)
        OCAMLFLAGS += -thread
        export
   

   This modification has two parts. First, it detects the MinGW toolchain to change the command line syntax of some of the build options. Second, it adjusts the OCaml warning flags so that the source compiles under 3.12.

8. Do make bootstrap
9. Edit .config to set your installation root
10. Do make all
11. Do make install

Good luck!

Smooth Operators

Edit: Of course the module Num is already present in the standard library. I've renamed the module to Arith.

The newly-released OCaml 3.12 includes many extensions to the sub-language of modules. One of the simplest but most practical is the syntax for locally opening modules (let open M in e), and for evaluating expressions in the context of an implicitly-opened module (M.(e), equivalent to the former). The biggest payoff this syntax affords is overloading operators and functions in an expression, in a delimited context denoted by a module used as a dictionary:

let degree n =
  let pi =  3.1415926535897931 in
  Arith.F.(2. * pi / 180. * of_int n)

Note that the operators are the usual ones! Another neat example:

let rgba r g b a =
  Arith.I32.((of_int r lsl 8 lor of_int g) lsl 8 lor of_int b) lsl 8 lor of_int a)

(I've purposefully written the example to showcase the operator precedence, not for clarity). Unfortunately, the standard library doesn't yet include the modules necessary for this to work. Here's my version of the built-in numeric instances, suitable for inclusion in your .ocamlinit file. It is structured as a top-level module Arith, but can be put into a arith.ml file for separate compilation (if you do that, take care to include in the .mli interface file the complete module signature, including externals, so that the compiler can inline the definitions). This module contains sub-modules with definitions for each of the types int, int32, int64, Big_int, float, and Ratio. Every sub-module conforms to the NUM signature (inspired by the type classes in Haskell's Prelude):

module type NUM = sig
 type t
 val min_value : t
 val max_value : t
 val of_int    : int -> t
 val to_int    : t -> int
 val of_string : string -> t
 val to_string : t -> string
 val ( ~- )    : t -> t
 val ( ~+ )    : t -> t
 val (  + )    : t -> t -> t
 val (  - )    : t -> t -> t
 val (  * )    : t -> t -> t
 val (  / )    : t -> t -> t
 val (mod )    : t -> t -> t
 val abs       : t -> t
end

so that with the following top-level definitions:

let show (type t) d =
  let module N = (val d : NUM with type t = t) in N.to_string

let read (type t) d =
  let module N = (val d : NUM with type t = t) in N.of_string

(note the syntax for modules as first-class values) the following code works:

# read (module Arith.I : NUM with type t = int) "123" ;;
- : int = 123
# read (module Arith.I32 : NUM with type t = int32) "123" ;;
- : int32 = 123l
# read (module Arith.I64 : NUM with type t = int64) "123" ;;
- : int64 = 123L
# read (module Arith.F : NUM with type t = float) "123" ;;
- : float = 123.

(the syntax for binding first-class module values is pretty heavy). They also conform to the ORD signature (also borrowed from Haskell):

module type ORD = sig
  type t
  val compare   : t -> t -> int
  val ( =  )    : t -> t -> bool
  val ( <> )    : t -> t -> bool
  val ( <  )    : t -> t -> bool
  val ( <= )    : t -> t -> bool
  val ( >  )    : t -> t -> bool
  val ( >= )    : t -> t -> bool
end

so that the following code is generic on the module implementing it:

let max (type t) d (x : t) (y : t) : t =
  let module N = (val d : ORD with type t = t) in
  N.(if x < y then y else x)

let min (type t) d (x : t) (y : t) : t =
  let module N = (val d : ORD with type t = t) in
  N.(if x < y then x else y)

The sub-modules have short, mnemonic names I, I32, I64, Z, F and Q so that they don't clash with the corresponding standard modules. The first four, the binary integral types, conform to the following BIN signature:

module type BIN = sig
  type t
  val succ   : t -> t
  val pred   : t -> t
  val (land) : t -> t -> t
  val (lor ) : t -> t -> t
  val (lxor) : t -> t -> t
  val lnot   : t -> t
  val (lsl ) : t -> int -> t
  val (lsr ) : t -> int -> t
  val (asr ) : t -> int -> t
end

So, for those of you that can't or won't avail yourselves to extension libraries like OCaml Batteries, here is the complete code for the module Arith:

module Arith = struct
  module I = struct
    type t = int
    let min_value      : t = 1 lsl (if 1 lsl 31 = 0 then 30 else 62)
    let max_value      : t = min_value - 1
    external of_int    : int -> t = "%identity"
    external to_int    : t -> int = "%identity"
    external of_string : string -> t = "caml_int_of_string"
    let      to_string : t -> string = Pervasives.string_of_int
    external ( ~- )    : t -> t = "%negint"
    external ( ~+ )    : t -> t = "%identity"
    external (  + )    : t -> t -> t = "%addint"
    external (  - )    : t -> t -> t = "%subint"
    external (  * )    : t -> t -> t = "%mulint"
    external (  / )    : t -> t -> t = "%divint"
    external (mod )    : t -> t -> t = "%modint"
    let abs  (x: t)    : t = if x >= 0 then x else -x
    let compare        : t -> t -> int  = Pervasives.compare
    let      ( =  )    : t -> t -> bool = Pervasives.( =  )
    let      ( <> )    : t -> t -> bool = Pervasives.( <> )
    let      ( <  )    : t -> t -> bool = Pervasives.( <  )
    let      ( <= )    : t -> t -> bool = Pervasives.( <= )
    let      ( >  )    : t -> t -> bool = Pervasives.( >  )
    let      ( >= )    : t -> t -> bool = Pervasives.( >= )
    external succ      : t -> t = "%succint"
    external pred      : t -> t = "%predint"
    external (land)    : t -> t -> t = "%andint"
    external (lor )    : t -> t -> t = "%orint"
    external (lxor)    : t -> t -> t = "%xorint"
    let lnot (x: t)    : t = x lxor (-1)
    external (lsl )    : t -> int -> t = "%lslint"
    external (lsr )    : t -> int -> t = "%lsrint"
    external (asr )    : t -> int -> t = "%asrint"
  end
  module I32 = struct
    type t = int32
    let min_value      : t = Int32.min_int
    let max_value      : t = Int32.max_int
    external of_int    : int -> t = "%int32_of_int"
    external to_int    : t -> int = "%int32_to_int"
    external of_string : string -> t = "caml_int32_of_string"
    let      to_string : t -> string = Int32.to_string
    external ( ~- )    : t -> t = "%int32_neg"
    external ( ~+ )    : t -> t = "%identity"
    external (  + )    : t -> t -> t = "%int32_add"
    external (  - )    : t -> t -> t = "%int32_sub"
    external (  * )    : t -> t -> t = "%int32_mul"
    external (  / )    : t -> t -> t = "%int32_div"
    external (mod )    : t -> t -> t = "%int32_mod"
    let abs  (x: t)    : t = if x >= 0l then x else -x
    let compare        : t -> t -> int  = Pervasives.compare
    let      ( =  )    : t -> t -> bool = Pervasives.( =  )
    let      ( <> )    : t -> t -> bool = Pervasives.( <> )
    let      ( <  )    : t -> t -> bool = Pervasives.( <  )
    let      ( <= )    : t -> t -> bool = Pervasives.( <= )
    let      ( >  )    : t -> t -> bool = Pervasives.( >  )
    let      ( >= )    : t -> t -> bool = Pervasives.( >= )
    let      succ      : t -> t = Int32.succ
    let      pred      : t -> t = Int32.pred
    external (land)    : t -> t -> t = "%int32_and"
    external (lor )    : t -> t -> t = "%int32_or"
    external (lxor)    : t -> t -> t = "%int32_xor"
    let lnot (x: t)    : t = x lxor (-1l)
    external (lsl )    : t -> int -> t = "%int32_lsl"
    external (lsr )    : t -> int -> t = "%int32_asr"
    external (asr )    : t -> int -> t = "%int32_lsr"
  end
  module I64 = struct
    type t = int64
    let min_value      : t = Int64.min_int
    let max_value      : t = Int64.max_int
    external of_int    : int -> t = "%int64_of_int"
    external to_int    : t -> int = "%int64_to_int"
    external of_string : string -> t = "caml_int64_of_string"
    let      to_string : t -> string = Int64.to_string
    external ( ~- )    : t -> t = "%int64_neg"
    external ( ~+ )    : t -> t = "%identity"
    external (  + )    : t -> t -> t = "%int64_add"
    external (  - )    : t -> t -> t = "%int64_sub"
    external (  * )    : t -> t -> t = "%int64_mul"
    external (  / )    : t -> t -> t = "%int64_div"
    external (mod )    : t -> t -> t = "%int64_mod"
    let abs  (x: t)    : t = if x >= 0L then x else -x
    let compare        : t -> t -> int  = Pervasives.compare
    let      ( =  )    : t -> t -> bool = Pervasives.( =  )
    let      ( <> )    : t -> t -> bool = Pervasives.( <> )
    let      ( <  )    : t -> t -> bool = Pervasives.( <  )
    let      ( <= )    : t -> t -> bool = Pervasives.( <= )
    let      ( >  )    : t -> t -> bool = Pervasives.( >  )
    let      ( >= )    : t -> t -> bool = Pervasives.( >= )
    let      succ      : t -> t = Int64.succ
    let      pred      : t -> t = Int64.pred
    external (land)    : t -> t -> t = "%int64_and"
    external (lor )    : t -> t -> t = "%int64_or"
    external (lxor)    : t -> t -> t = "%int64_xor"
    let lnot (x: t)    : t = x lxor (-1L)
    external (lsl )    : t -> int -> t = "%int64_lsl"
    external (lsr )    : t -> int -> t = "%int64_asr"
    external (asr )    : t -> int -> t = "%int64_lsr"
  end
  module Z = struct
    type t = Big_int.big_int
    let min_value   : t = Big_int.zero_big_int
    let max_value   : t = Big_int.zero_big_int
    let of_int      : int -> t = Big_int.big_int_of_int
    let to_int      : t -> int = Big_int.int_of_big_int
    let of_string   : string -> t = Big_int.big_int_of_string
    let to_string   : t -> string = Big_int.string_of_big_int
    let ( ~- )      : t -> t = Big_int.minus_big_int
    external ( ~+ ) : t -> t = "%identity"
    let (  + )      : t -> t -> t = Big_int.add_big_int
    let (  - )      : t -> t -> t = Big_int.sub_big_int
    let (  * )      : t -> t -> t = Big_int.mult_big_int
    let (  / )      : t -> t -> t = Big_int.div_big_int
    let (mod )      : t -> t -> t = Big_int.mod_big_int
    let abs         : t -> t = Big_int.abs_big_int
    let compare     : t -> t -> int  = Big_int.compare_big_int
    let ( =  )      : t -> t -> bool = Big_int.eq_big_int
    let ( <> )      (x:t) (y:t) = not (x = y)
    let ( <  )      : t -> t -> bool = Big_int.lt_big_int
    let ( <= )      : t -> t -> bool = Big_int.le_big_int
    let ( >  )      : t -> t -> bool = Big_int.gt_big_int
    let ( >= )      : t -> t -> bool = Big_int.ge_big_int
    let succ        : t -> t = Big_int.succ_big_int
    let pred        : t -> t = Big_int.pred_big_int
    let (land)      : t -> t -> t = Big_int.and_big_int
    let (lor )      : t -> t -> t = Big_int.or_big_int
    let (lxor)      : t -> t -> t = Big_int.xor_big_int
    let lnot        : t -> t = let m1 = of_int (-1) in fun x -> x lxor m1
    let (lsl )      : t -> int -> t = Big_int.shift_left_big_int
    let (lsr )      : t -> int -> t = Big_int.shift_right_big_int
    let (asr )      : t -> int -> t = Big_int.shift_right_towards_zero_big_int
  end
  module F = struct
    type t = float
    let min_value      : t = Int64.float_of_bits 0xFF_F0_00_00_00_00_00_00L
    let max_value      : t = Int64.float_of_bits 0x7F_F0_00_00_00_00_00_00L
    external of_int    : int -> t = "%floatofint"
    external to_int    : t -> int = "%intoffloat"
    external of_string : string -> t = "caml_float_of_string"
    let      to_string : t -> string = Pervasives.string_of_float
    external ( ~- )    : t -> t = "%negfloat"
    external ( ~+ )    : t -> t = "%identity"
    external (  + )    : t -> t -> t = "%addfloat"
    external (  - )    : t -> t -> t = "%subfloat"
    external (  * )    : t -> t -> t = "%mulfloat"
    external (  / )    : t -> t -> t = "%divfloat"
    external (mod )    : t -> t -> t = "caml_modf_float"
    let abs  (x: t)    : t = if x >= 0. then x else -x
    external compare   : t -> t -> int = "%compare"
    external ( =  )    : t -> t -> bool = "%equal"
    external ( <> )    : t -> t -> bool = "%notequal"
    external ( <  )    : t -> t -> bool = "%lessthan"
    external ( <= )    : t -> t -> bool = "%lessequal"
    external ( >  )    : t -> t -> bool = "%greaterthan"
    external ( >= )    : t -> t -> bool = "%greaterequal"
  end
  module Q = struct
    type t = Ratio.ratio
    let min_value   : t =
      let flag = Arith_status.get_error_when_null_denominator () in
      Arith_status.set_error_when_null_denominator false;
      let v = Ratio.minus_ratio (Ratio.create_ratio Big_int.unit_big_int Big_int.zero_big_int) in
      Arith_status.set_error_when_null_denominator flag;
      v
    let max_value   : t =
      let flag = Arith_status.get_error_when_null_denominator () in
      Arith_status.set_error_when_null_denominator false;
      let v = Ratio.create_ratio Big_int.unit_big_int Big_int.zero_big_int in
      Arith_status.set_error_when_null_denominator flag;
      v
    let of_int      : int -> t = Ratio.ratio_of_int
    let to_int      : t -> int = Ratio.int_of_ratio
    let of_string   : string -> t = Ratio.ratio_of_string
    let to_string   : t -> string = Ratio.string_of_ratio
    let ( ~- )      : t -> t = Ratio.minus_ratio
    external ( ~+ ) : t -> t = "%identity"
    let (  + )      : t -> t -> t = Ratio.add_ratio
    let (  - )      : t -> t -> t = Ratio.sub_ratio
    let (  * )      : t -> t -> t = Ratio.mult_ratio
    let (  / )      : t -> t -> t = Ratio.div_ratio
    let (mod ) (x:t) (y:t) : t =
      Ratio.sub_ratio x 
        (Ratio.mult_ratio y
          (Ratio.ratio_of_big_int
            (Ratio.floor_ratio
              (Ratio.div_ratio x y))))
    let abs         : t -> t = Ratio.abs_ratio
    let compare     : t -> t -> int  = Ratio.compare_ratio
    let ( =  )      : t -> t -> bool = Ratio.eq_ratio
    let ( <> ) (x:t) (y:t) = not (x = y)
    let ( <  )      : t -> t -> bool = Ratio.lt_ratio
    let ( <= )      : t -> t -> bool = Ratio.le_ratio
    let ( >  )      : t -> t -> bool = Ratio.gt_ratio
    let ( >= )      : t -> t -> bool = Ratio.ge_ratio
  end
end

In the case of Z, there are no meaningful extremal values. I haven't included a module for NativeInt, but you can do so quite easily. Note that, if any of the external functions in the standard library changes, this module must be revised. I hope you find it useful.