## 2010-08-22

### 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 `One`s, 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.

## 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 |> 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.

## 2010-08-16

### 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
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 =

.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
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!

## 2010-08-14

### 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.

## 2010-08-05

### Reviving an Old Tiger

An old machine that proved its mettle on the line can be a handy development server, on a pinch. Especially if you're starting up by pulling your boot straps, as I currently am. I have this Blue & White G3 that served me faithfully for the last, say, 10 years. Bitrot, alas, is not a hardware problem: software version numbers climb and software authors drop support for older operating systems and configurations, and we misers are left struggling and scavenging for information to make things compile and install. So, for my own reference, here's what I did this time. This applies to Mac OS X 10.4.11, AKA Tiger:

Sybase 12
Get the latest EBF for Mac OS, EBF17473. It works beautifully.
XCode 2.5
I had to root quite a bit around the newly redesigned Apple Developer site. The image name is xcode25_8m2558_developerdvd.dmg
MySQL 5.1.49
A challenge for GCC 4.0.1, it kernel-panicked the machine once. I followed these fine instructions. I set it up to start up automatically on boot, via the following launchd script:
```
<!DOCTYPE plist PUBLIC "-//Apple Computer//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
<key>KeepAlive</key>
<true/>
<key>Label</key>
<string>com.mysql.mysqld</string>
<key>Program</key>
<string>/usr/local/mysql/bin/mysqld_safe</string>
<true/>
<string>mysql</string>
<key>WorkingDirectory</key>
<string>/usr/local/mysql</string>
</dict>
</plist>
```

Put it in /Library/LaunchDaemons/com.mysql.mysqld.plist.

Apache httpd 2.2.16
I followed these instructions. The layout I used is this:
```<Layout DarwinLocal>
prefix:        /usr/local/apache2
exec_prefix:   \${prefix}
bindir:        \${exec_prefix}/bin
sbindir:       \${exec_prefix}/sbin
libdir:        \${exec_prefix}/lib
libexecdir:    \${exec_prefix}/modules
mandir:        \${prefix}/man
sysconfdir:    /etc/httpd
htdocsdir:     /Library/WebServer/Documents
cgidir:        /Library/WebServer/CGI-Executables
includedir:    \${prefix}/include+
localstatedir: /var
runtimedir:    \${localstatedir}/run
logfiledir:    \${localstatedir}/log/httpd
proxycachedir: \${runtimedir}/proxy
</Layout>
```

and the configuration is this (culled from here):

```CFLAGS="-arch ppc -isysroot /Developer/SDKs/MacOSX10.4u.sdk" ./configure \
--enable-layout=DarwinLocal \
--enable-access \
--enable-actions --enable-alias --enable-asis --enable-auth \
--enable-auth_dbm --enable-auth_digest --enable-autoindex \
--enable-cache --enable-cgi --enable-dav --enable-dav_fs \
--enable-deflate --enable-dir --enable-disk_cache \
--enable-dumpio --enable-env --enable-expires --enable-fastcgi \
--enable-include --enable-info --enable-log_config \
--enable-log_forensic --enable-logio --enable-mem_cache --enable-mime \
--enable-mime_magic --enable-negotiation --enable-perl \
--enable-rewrite --enable-setenvif --enable-speling --enable-ssl \
--enable-status --enable-suexec --enable-unique_id --enable-userdir \
--enable-usertrack --enable-version --enable-vhost_alias --enable-so \
--enable-module=all --enable-shared=max
```

These instructions allow automatic launching of Apache at startup.

zlib 1.2.5
libpng 1.4.3
Beware, as the DLL gets installed with the wrong name: it should be libpng14.14.dylib.
jpegsrc v8b
freetype 2.4.1
gd-2.0.35
I configured it with the usual caveats.
libmcrypt 2.5.8
mhash 0.9.9.9
mcrypt-2.6.8
php 5.3.3
It took me quite a long while sort out the correct incantation to configure PHP. This is what worked for me:
```export CFLAGS="-DSQLITE_ENABLE_LOCKING_STYLE=0 -DBIND_8_COMPAT"
./configure \
-prefix=/usr/local/php5 \
-with-config-file-path=/etc \
-with-zlib=/usr/local \
-with-xml \
-with-xsl \
-enable-ctype \
-enable-dom \
-enable-exif \
-enable-filter \
-enable-ftp \
-enable-gd-native-ttf \
-enable-libxml \
-enable-mbregex \
-enable-mbstring \
-enable-pcntl \
-enable-pdo \
-enable-posix \
-enable-shmop \
-enable-simplexml \
-enable-soap \
-enable-xml \
-enable-bcmath \
-with-bz2=/usr/bin \
-with-curl \
-with-freetype-dir=/usr/local \
-with-gd=/usr/local \
-with-iconv \
-with-jpeg-dir=/usr/local \
-with-ldap \
-with-mcrypt=/usr/local \
-with-mysql=/usr/local/mysql \
--with-mysqli=/usr/local/mysql/bin/mysql_config \
-with-openssl \
-with-pdo-mysql=/usr/local/mysql \
-with-png-dir=/usr/local \
-with-zlib=/usr/local \
-enable-dbx \
-enable-sockets \
-with-apxs2=/usr/local/apache2/sbin/apxs \
-with-kerberos=/usr \
-with-mysqlsock=/var/mysql/mysql.sock \
-without-pear
```

Don't forget to apply the patch described in this post. Be sure to make test!

Next, configure Apache to run phpMyAdmin, Drupal and Mantis (I won't have anything to do with either Python or Ruby, sorry). I expect this old Tiger to bend under the pressure but not break.