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

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.

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

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>
 <key>RunAtLoad</key>
 <true/>
 <key>UserName</key>
 <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
    datadir:       /Library/Documents
    sysconfdir:    /etc/httpd
    installbuilddir: ${datadir}/build
    errordir:      ${datadir}/error
    iconsdir:      ${datadir}/icons
    htdocsdir:     /Library/WebServer/Documents
    manualdir:     ${datadir}/manual
    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-file_cache --enable-headers --enable-imap \
--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.