OCaml and typeful programming: an annotated bibliography (of sorts)

I cannot help but feel somewhat envious at the high level of expertise that the Haskell community display at effectively using the advanced type system the language provides. Many of the techniques are not applicable to OCaml, which lacks higher-ranked polymorphism. Some of these techniques, however, can be translated to OCaml, but these seem to be more folklore than codified practice, and finding material about it feels like a fishing expedition.

Aside: SML is as amenable as OCaml to these techniques, and some are more standard in the former than in the latter; in particular, MLton's Basis and additional libraries are a marvel of elegance and power, and in my opinion should guide OCaml's library long-term design. It would be a nice project, a re-implementation of ML's Basis for OCaml that replaced its standard library, if only to incorporate MLton's extended library.

So, for the record, here's a list of pointers (I dare not call this an "annotated bibliography") to some of the "tricks", for easy retrieval and study.

The Expression Problem

Jacques Garrigue's solution is canonical, and the basic use case for polmorphic variants. Dually, Didier Rémy uses objects.

• Garrigue, Jacques. Private rows: abstracting the unnamed (2006), online
• — Simple Type Inference for Structural Polymorphism (2002), online
• Overview at Lambda the Ultimate
• Rémy & Vuillon, On the (un)reality of virtual types (2000), online
• Rémy's code for the above

Haskell vs. OCaml

It is known that Haskell type classes can be encoded as ML modules and functors (Kisyelov and Shan's Translucent Functors).

• Caml list
• Lambda the Ultimate
• A simpler encoding
• Oleg on the type of the Continuation Monad
• Oleg critiques monads on the OCaml list and Lambda the Ultimate

Existential types

The poor man's approach to existential types is to use polymorphic variants. However, although it might seem as hackery, objects encode the existential parameter via the type of self, as Oleg points out repeatedly:

• Oleg's explanation
• Another Oleg post
• Jacques' introduction
• Oleg's elimination
• A full and faithful encoding of Haskell existentials
• OCaml as Scheme
• Encoding via references

Polymorphic recursion

Either through references or polymorphic records, Oleg is a master wizard:

• Arrows, on the Caml List
• Existentials, on the Caml List
• Julien Signole's many forms of type-sound Ω
• Oleg's typed fixpoint combinators

Phantom types

There's much written about phantom types and their application to verify static lightweight capabilities. A collection of techniques and applications:

• Oleg's sprintf on the Caml List
• Capabilities, and number-parameterized types
• Polymorphic variants and structural subtyping of capabilities
• Stepwise definition of records
• Yaron Minsky's overview
• Typed relational algebra

As you can see, Oleg (who really has a last name) seems to run Hindley-Milner as a background thought process. His page on ML writings and code is fully worth of study.

Edit: I found a couple of references more too good to let pass.

Edit 2: Oleg is a treasure trove of insight…

Splitting Hairs

It is often claimed that the formal derivation of an algorithm hand-in-hand with its specification is too hard to do, so that it is only viable for toy examples. I have found, as Dijkstra repeatedly has, that discipline and restraint in the drive to "just code" are key to succeeding. As an example, I'll show the creation from scratch of a program I didn't know before.

Aside: You'll have to believe me on this, but I first attempted to code this program without paying attention to the logic; it had a bug. Instead of trying to paper over it with some fix or other, I started from scratch. Apart from some minor omissions, due more to inattention to the predicates than anything else, it worked on the first try.

This program generates the partitions of an integer n in reverse lexicographical (or colex) order. As I did before, I choose to write it in imperative OCaml, with each generated value being fed to a continuation; this allows straightforward translation to many other languages without the need to fake or build functional features in. The first question I must answer is what is an adequate logical description of a partition? "Adequate" here means the weakest (that is, least constraining) predicate that completely defines a partition.

I'll keep the partition of n as an array v of monotonically non-increasing, positive values that sum to n. The predicate that characterizes a partition is:

P ≡ ⟨∑ i : 0 ≤ i < n : v.i⟩ = n ∧ ⟨∀ i, j : 0 < i < j < n : v.i ≥ v.j > 0⟩

That is a mouthful, and —more worryingly— is over-constrained. Any partition might have less than n elements; in fact most will. The standard operating procedure is to change a constant by a variable and parameterize the predicate by it, call it l. In the process, I'll split the predicate in two:

S.l ≡ ⟨∑ i : 0 ≤ i < l : v.i⟩ = n
T.l ≡ ⟨∀ i, j : 0 < i < j < l : v.i ≥ v.j > 0⟩

so that P.l ≡ S.l ∧ T.l. Now v.0 = n ∧ l = 1 immediately satisfy P.l, and so I can begin with a program scheme:

let part_iter n (f : int array -> int -> unit) =
  let v = Array.make n 0
  and l = ref 1 in
  v.(0) <- n;
  (* P.l *)
  f v !l;
  Generate the partitions in colex order
  (* P.n *)

The kernel of the code must change both v and l stepwise, such that the last partition is found when l = n; this will be our stopping condition:

let part_iter n (f : int array -> int -> unit) =
  let v = Array.make n 0
  and l = ref 1 in
  v.(0) <- n;
  (* P.l *)
  f v !l;
  while !l != n do
    Advance v and l to the next partition in colex order
    (* P.l *)
    f v !l
  done
  (* P.n *)

Think of the partition as a row of piles of stones or marbles, in non-increasing order. To respect the colex order, the change must be done as far to the right as possible, and must be a decrement of the last pile that can be so altered, under invariance of T.l:

let part_iter n (f : int array -> int -> unit) =
  let v = Array.make n 0
  and l = ref 1 in
  v.(0) <- n;
  (* P.l *)
  f v !l;
  while !l != n do
    let j = ref (!l - 1) in
    while v.(!j) == 1 do v.(!j) <- 0; decr j done;
    v.(!j) <- v.(!j) - 1;
    Restore S.l under invariance of T.l
    (* P.l *)
    f v !l
  done
  (* P.n *)

The inner loop picks up the singleton piles that cannot possibly be decremented, until finding one pile that can. Or rather, picking up singleton piles is decrementing them; if OCaml had repeat… until loops, the inner loop could be written more compactly as:

let j = ref !l in
repeat decr j; v.(!j) <- v.(!j) - 1 until v.(!j) != 0;
Restore S.l…

In order to keep the partition to sum to n, the l - j picked-up stones must be added back under invariance of T.l:

let part_iter n (f : int array -> int -> unit) =
  let v = Array.make n 0
  and l = ref 1 in
  v.(0) <- n;
  (* P.l *)
  f v !l;
  while !l != n do
    let j = ref (!l - 1) in
    while v.(!j) == 1 do v.(!j) <- 0; decr j done;
    v.(!j) <- v.(!j) - 1;
    let s = ref (!l - !j) in
    incr j;
    while !s != 0 do
      Add back s under invariance of T.l
    done;
    (* S.j *)
    l := !j;
    (* P.l *)
    f v !l
  done
  (* P.n *)

Invariance of T.l means that we must not add more stones than the previous pile has:

let part_iter n (f : int array -> int -> unit) =
  let v = Array.make n 0
  and l = ref 1 in
  v.(0) <- n;
  (* P.l *)
  f v !l;
  while !l != n do
    let j = ref (!l - 1) in
    while v.(!j) == 1 do v.(!j) <- 0; decr j done;
    v.(!j) <- v.(!j) - 1;
    let s = ref (!l - !j) in
    incr j;
    while !s != 0 do
      v.(!j) <- min v.(!j - 1) !s;
      s := !s - v.(!j);
      incr j
    done;
    (* S.j *)
    l := !j;
    (* P.l *)
    f v !l
  done
  (* P.n *)

That's it. On a personal note, I'm not so much proud that I could write this program, but rather that I've learned enough of Dijkstra's discipline to put it to effective use.

Aside: Now that I read it, I don't think the sarcastic overtones of the title are in the spirit of this article. I chose it at the beginning as a pun on integer partitions; someone may construe it as a disparaging remark on the level of attention to detail needed to formally derive programs. If so, their loss; to me, the confidence gained by such hair-splitting is reassuring.

Generating Combinations

Only for the record, and because I arrived at this form of the algorithm after massaging the one given in Algorithms for Programmers, Algorithm 6.1 "Lexicographic and Co-Lexicographic Order" and I find it very pretty. First the algorithm, then the explanation:

let iter_comb n k (f : int array -> unit) =
  let v = Array.init k (fun i -> i) in
  f v;
  while v.(0) != n - k do
    let j = ref (k - 1) in
    while v.(!j) == n - k + !j do decr j done;
    let z = v.(!j) - !j + 1 in
    while !j != k do
      v.(!j) <- z + !j;
      incr j
    done;
    f v
  done

Since the number of combinations grows factorially, I opted to write a generator instead of something returning a list. The continuation f will receive each of the combinations of k elements taken from a set of n elements, with each represented as an integer between 0 and n - 1.

Aside: This means that it can be translated to Python, say, via a direct syntactic mapping:

def comb(n, k):
  v = range(0, k)
  yield v
  while v[0] != n - k:
    j = k - 1
    while v[j] == n - k + j:
      j -= 1
    z = v[j]
    while j != k:
      z += 1
      v[j] = z
      j += 1
    yield v
  return

I've nominally faked that with the help of a cheat sheet.

These subsets are in turn represented as an integer array sorted in ascending order, and each combination will be lexicographically the successor to the previous one. This is what is normally called lex-order generation.

Taken together, these two preconditions determine univocally what the algorithm does. The lexicographically first combination satisfying these preconditions is {0, 1, … k - 1 }; this is built on line 2 and passed to the generator's continuation f on line 3. Dually, the lexicographically last combination is { n - k, n - k + 1, … n - 1 }; this gives us the loop invariant:

P ≡ ⟨∃i : 0 ≤ i < k : v.(i) ≠ n - k + i⟩

The loop condition on line 4 takes advantage of this. The inner loop then sets to change the last element on the subset that can possibly be changed, so it has to find it. The loop on line 6 looks for the greatest j such that all elements to the right of j have their maximum allowed value, so that:

Q ≡ v.(j) ≠ n - k + j ∧ ⟨∀i : j < i < k : v.(i) = n - k + i⟩

and the loop condition imply P, and so v.(j) can be incremented without violating the invariant; the next elements must be changed to restore it fully. Note that in line 7, the increment is 1 ≤ z ≤ n - k, so the algorithm makes progress on each iteration.

Aside: The upper bound for z follows from straightforward algebraic manipulation; the lower bound stems from the fact that the minimum value that v.(j) can take after the execution of line 7 is 0, but only for j = 0 since the subset is sorted.

This algorithm, when specialized to k = n, is equivalent to Dijkstra's algorithm for the Next Lexicographic Permutation (A Discipline of Programming, Prentice-Hall, 1997.)

Bitwise Dice

I'm rereading this paper by Knuth and Yao [1], which could be called "How to throw a die when all you have is a penny", or something. Its premise is, how can you generate a random variable with arbitrary distribution when all you have is a perfectly fair binary random variate? It begins with this blindingly eye-catching diagram:

Every round node is a coin-toss (a bit-flip), and transitions are taken depending on the value obtained, until one of the dice nodes are reached. What's the expected number of flips needed to get a die? As explained in the paper, it's T = 3 + 2/8⋅T, which solves for T = 4. After this preliminaries, they show us another diagram, but not before observing that [t]he reader may have noticed a source of inefficiency in [the figure]: When three equal values are obtained, we could have used this common result as the value of the next flip, since 000 and 111 are equally probable.

I certainly hadn't; the paper states that the average number of bit-flips needed is 11/3, and that that is minimal. The rest of the paper is devoted to prove constructively that this is so, by giving an algorithm that minimizes the number of bit-flips required to compute an arbitrary random variate. What it doesn't show is how to arrive at this number of flips. Applying the method cited above, we have T = 1 + U and U = 2 + 1/4⋅U, for U = 8/3, T = 11/3.

All fine and dandy but, why am I writing this? For one, to show you pretty finite state machines (actually, Markov chains) that generate dice throws! You might think, what a roundabout way to do it, and counter with:

let die () = 1 + Random.int 6

One problem I see is that, as usually implemented, it is easier to find in the wild fairer bits than dice; or rather, usual implementations of integer random variates tend to take the lower bits from a linear congruential generator, which is a rather lousy way to do it. It is better to do:

let bit () = Random.float 1. < 0.5

which, as it takes into account the more significant bits first, is more apt to be fairer. Another good source of random bits is a linear feedback shift register; the table in [2, 376] shows that x³¹ + x³ + 1 is a primitive polynomial, modulo 2, which gives the following generator with period 2³¹ - 1:

let seed = ref 0x33c6ef37

let set_seed s =
  seed := if s == 0 then 0x33c6ef37 else s

let rand_bit () =
  let b = !seed land 1 in
  seed := (!seed lsr 1) lxor (-b land 0x40000004);
  b

Of course, if you can control your source of bits this disquisition is probably moot; if not, it might be something you'd want to account for. Anyway, back to the bones. There are many ways to write a FSM, but most involve using a table. Instead of falling so low, I'll show you a little functional magic. A state is a finite map from an input symbol to an edge or transition; in turn, an edge can be a way to get to the next state or a final, result symbol:

type ('a, 'b) state = 'a -> ('a, 'b) edge
 and ('a, 'b) edge  = Halt of 'b | Next of ('a, 'b) state

I'll represent the second machine as a value of type (bool, int) state, with maximally-shared states via value recursion. I number the states from left to right, and from top to bottom:

let die_fsm : (bool, int) state =
  let
  rec st0 = function false -> Next st1 | true -> Next st2
  and st1 = function false -> Next st3 | true -> Next st4
  and st2 = function false -> Next st5 | true -> Next st6
  and st3 = function false -> Next st1 | true -> Halt 1
  and st4 = function false -> Halt 2   | true -> Halt 3
  and st5 = function false -> Halt 4   | true -> Halt 5
  and st6 = function false -> Halt 6   | true -> Next st2
  in st0

The state machine is run simply via the following function:

let rec run_fsm st input =
  match st (input ()) with
  | Next st -> run_fsm st input
  | Halt x  -> x

That's it, really! I can throw my die like so:

let die () = run_fsm die_fsm (fun () -> rand_bit () == 1)

Let's see how fair our die is. For that, I'll compute a histogram of recorded values in an experiment involving n throws:

let test_die n =
  let hist = Array.make 6 0 in
  for i = 1 to n do
    let d = die () - 1 in
    hist.(d) <- hist.(d) + 1
  done;
  Array.map (fun s -> float s /. float n) hist

You can check that the die is fair:

# test_die 100_000 ;;
- : float array = [|0.16379; 0.16713; 0.16702; 0.16768; 0.1661; 0.16828|]

And of course, let's make sure I haven't made a silly mistake:

# Array.fold_left (+.) 0. (test_die 100_000) ;;
- : float = 1.

Now, shoot!

References

1. Knuth, D.E.K. and Yao, A. C. The Complexity of Nonuniform Random Number Generation. Reprinted in Donald E. Knuth, Selected Papers on Analysis of Algorithms (Stanford: CSLI lecture notes 102, 2000).
2. Bruce Schneier, Applied Cryptography Second Edition: protocols, algorithms, and source code in C (New York: John Wiley & Sons, Inc. 1996)

Thinking Inside the Box

There's a non-trivial algorithm in Computer Graphics, the so-called Kay-Kajiya test, that is actually trivial to derive by carefully thinking about the problem it solves. A axis-aligned box is the 3-dimensional generalization of a closed interval. Intuitively, it's a rectangular box whose six sides are parallel to the three axes; formally, given points P = (p_x, p_y, p_z) and Q = (q_x, q_y, q_z), it is the set of points B = { X = (x, y, z) | p_x ≤ x ≤ q_x ∧ p_y ≤ y ≤ q_y ∧ p_z ≤ z ≤ q_z }. As you can see, it is the "product" of three real intervals; as such, it can be generalized for any number of dimensions, but this would require an uncountable set of subscripts, which is not really practical. Pragmatically, I'll resort to naturally-indexed sets of coordinates—arrays:

type point = float array
type vect  = float array

The algorithm is in fact generic in the number of dimensions:

let dim = 3

With that, a box is just the left-bottom-front ("low") and the right-top-back ("high") points:

type bbox  = { l : point; h : point; }

A parametric line is given by a direction vector and a point belonging to the line:

type line  = { p : point; v : vect ; }

Now, the line l intersects the box B if and only if they have a point in common. This can have a set-based expression l ∩ B ≠ ∅, or a predicate-based existential expression ⟨∃X :: X ∈ l ∧ X ∈ B⟩ which is more amenable to formal manipulation:

   ⟨∃X :: X ∈ l ∧ X ∈ B⟩
≡ { parametricity of line, definition of box }
   ⟨∃X :: ⟨∃t : t ∈ R : X = l.p + t⋅l.v ⟩ ∧ ⟨⋀i : 0 ≤ i < D : B.l.i ≤ X.i ≤ B.h.i ⟩⟩
≡ { distributivity of ∧ over ∃ }
   ⟨∃X :: ⟨∃t : t ∈ R : X = l.p + t⋅l.v ∧ ⟨⋀i : 0 ≤ i < D : B.l.i ≤ X.i ≤ B.h.i ⟩⟩⟩
≡ { interchange }
   ⟨∃t : t ∈ R : ⟨∃X :: X = l.p + t⋅l.v ∧ ⟨⋀i : 0 ≤ i < D : B.l.i ≤ X.i ≤ B.h.i ⟩⟩⟩
≡ { one-point rule, defn. vector, point }
   ⟨∃t : t ∈ R : ⟨⋀i : 0 ≤ i < D : B.l.i ≤ l.p.i + t⋅l.v.i ≤ B.h.i ⟩⟩
≡ { algebra }
   ⟨∃t : t ∈ R : ⟨⋀i : 0 ≤ i < D : (B.l.i - l.p.i)/l.v.i ≤ t ≤ (B.h.i - l.p.i)/l.v.i⟩⟩

This is a set of D simultaneous linear inequalities. Any solution t must then satisfy the most restrictive of the inequalities, that is, their extreme bounds:

⇐ { upper and lower bounds }
   ⟨∃t : t ∈ R : ⟨max i : 0 ≤ i < D : (B.l.i - l.p.i)/l.v.i⟩ ≤ t ≤ ⟨min i : 0 ≤ i < D : (B.h.i - l.p.i)/l.v.i⟩⟩
≡ { real interval }
   ⟨max i : 0 ≤ i < D : (B.l.i - l.p.i)/l.v.i⟩ ≤ ⟨min i : 0 ≤ i < D : (B.h.i - l.p.i)/l.v.i⟩

There are a number of complications, though. The use of the parametric definition of the line makes implicit use of the fact that it is not really a line but an oriented ray; this means that if the box is "behind" the ray it won't be hit by the test. The solution for this is to sort the extremes to be tested. Also, if a vector component is zero the test must explicitly decide (that is, test to avoid dividing by zero) if a ray belonging to the side but not to the volume is actually inside or not the box. With these caveats, the following code is self-explanatory:

let intersects l b =
  let rec loop i hither thither =
    if i == dim then hither <= thither else
    let v, p, l, u = l.v.(i), l.p.(i), b.l.(i), b.h.(i) in
    if v <> 0. then
      let t0, t1 =
        let t0, t1 = (l -. p) /. v, (u -. p) /. v in
        if t0 < t1 then t0, t1 else t1, t0 in
      let hither  = max hither  t0
      and thither = min thither t1 in
      if hither > thither then false else
      loop (i + 1) hither thither
    else if l > p || p > u then false else
    loop (i + 1) hither thither
  in loop 0 neg_infinity infinity

The usual explanation of the algorithm is both motivated by and restricted to an appeal to geometric handwaving. A simple manipulation of the definition makes the derivation automatic and forced.

The Castle of Glyphs

Well, in English they're not called castles, but rooks. Surprisingly, the castling move is called enroque in Spanish, which is cognate to rook. Suppose you want to find non-self-intersecting closed rook's tours on a m-by-n chessboard. How would you go about it? But first, why would you want to do that?

I've found they make pretty linear patterns, somewhat reminiscent of arabesques and square Kufic script. For instance, the closed tours on a 4-by-4 chessboard are:

and some of the 1072 closed rook tours on a 6-by-6 chessboard are:

It is convenient to think of the board as a collection of cells accessible according to the rules governing the movement of a given piece. In this way, a piece's movements and a given board size give rise to a leap graph, viewed as a collection of vertices connected one another through edges:

type vertex = {
          cell : int * int;
  mutable next : vertex list;
  mutable deg  : int;
  mutable free : bool;

The cell are its coordinates in the board, the next list links together the vertex neighbors; deg is that list length (for faster computation), and free is a mark that will be used in traversing the graph. Given a definition of how a piece moves and a board size, I build the leap graph:

let board moves m n =

First, I preallocate an array of unconnected vertices:

  let size = m * n in
  let gg = Array.init size (fun j ->
    { cell = (j / n, j mod n); next = []; deg = 0; free = true; })
  in

Then, I thread the cells into a graph. For that, from each cell's (r, c) coordinate I find the neighboring cells reachable by applying the corresponding move, represented as a (dr, dc) shift, taking care of not falling outside the board:

  Array.iter (fun v ->
    let r, c = v.cell in
    List.iter (fun (dr, dc) ->
      let r', c' = r + dr, c + dc in
      if 0 <= r' && r' < m && 0 <= c' && c' < n then begin
        v.deg  <- v.deg + 1;
        v.next <- gg.(n * r' + c') :: v.next
      end) moves;
    ) gg;
  Array.to_list gg

There's always the tension between the convenience of naming each member of a datum and the implicit pattern matching afforded by function. In any case, having the vertices already created makes representing the edges as shared references to neighbors easy. The end result is that the board is represented as the list of linked cells.

In the full program I output the solutions graphically to a PostScript file. In order to not get mired into details, I'll abstract the output procedure and write the tour-finding as a higher order function, in the style of an iterator:

let tour out board =

A visited cell gets marked, and its out-degree decremented to record the fact that we entered it:

  let visit v =
    v.free <- false;
    v.deg  <- v.deg - 1

Backtracking must restore the cell's previous state by undoing the visit:

  and unvisit v =
    v.deg  <- v.deg + 1;
    v.free <- true
  in

A tour must begin somewhere, and the first cell in the vertex list is as good candidate as any other. Also, as the code finds valid tours it will keep track of the generated solutions:

  let first = List.hd board
  and sols = ref 0 in

Now, the generation proceeds cell by cell, by trying appending to the current tour a cell reachable from v. The easiest way to know when a tour is complete is to count the number of remaining cells to visit, that's rem:

  let rec advance tour rem v =

The next cell in the tour is, precisely and as a precondition, v:

    let tour = v.cell :: tour
    and rem  = pred rem in

A tour is, by definition, a sequence of cells visited one by one according to the rules for moving the piece, without repetition, which visits the entire board and returns to the starting place. If one is found, it is recorded and output:

    if rem == 0 && List.memq first v.next then begin
      incr sols;
      out tour

Otherwise, I mark the current cell as visited and try to extend the tour:

    end else begin
      visit v;

As a simple heuristic to prune the search space, I try first forced cells, that is, unvisited neighboring cells with only one way to go through them:

      begin try
        let force = List.find (fun w -> w.free && w.deg == 1) v.next in
        advance tour rem force

If no such forced cell is found, I expand the search tree with all the unvisited neighbors to the current vertex and try each in turn:

      with Not_found ->
        let next = List.filter (fun w -> w.free) v.next in
        List.iter (advance tour rem) next
      end;

Since the search is exhaustive, I have to restore the graph to the state it was upon entering the search, by un-visiting the current cell:

      unvisit v
    end
  in

How does the ball gets started? By the beginning, of course:

  visit first;
  advance [first.cell] (pred (List.length board)) (List.hd first.next);

Then, the graph is restored and the we return the solution count:

  unvisit first;
  !sols

A rook can move any number of cells vertically or horizontally; however, for doing so it must visit every intervening cell. Hence, it's best to make it move just one cell in each orthogonal direction: what we have is not a rook but the Wazir of Fantasy Chess:

let rook   = [  1,  0;  0,  1;  0, -1; -1,  0; ]

And now we that have all the pieces together, we could ask how many tours there are an a 4-by-6 chessboard:

# tour (fun _ -> ()) (board rook 4 6) ;;
- : int = 37

Which is odd, because some symmetries are taken into account. Can you tell which? Here's a hint:

They do look like letters in a strange script…

ocamlsdl on MacOS X 10.5 "Leopard"

I've found that there a number of pitfalls that make getting ocamlsdl up and running on Leopard a less than straightforward experience. For the record, here are a number of fixes I found I needed to apply. I'm reconstructing the process after the fact, so I apologize if anything is missing.

0. Prepare your environment

You'll need to set up some environment variables first. I'm a tcsh user, while the default in Leopard is bash; hence, you'll have to modify the environment yourself depending on your shell.

Include X11 in your executable path

libpng and freetype2 live inside /usr/X11. The standard way to pass linker options is to use libpng-config and freetype-config, these are in /usr/X11/bin. Add this to your binary path.

Fix broken Leopard linker

Set and export LDFLAGS with value

-dylib_file \
  /System/Library/Frameworks/OpenGL.framework/Versions/A/Libraries/libGL.dylib:\
  /System/Library/Frameworks/OpenGL.framework/Versions/A/Libraries/libGL.dylib

(this is one long option, broken into lines for ease of reading.)

1. Get SDL to compile

SDL proper builds and installs without problems; however, the tests need manual intervention.

1. Enter the test directory and ./configure.
2. Then manually edit Makefile and append $(LDFLAGS) to CFLAGS (line 7).
3. Finally make and run the tests. A good test to try is testwm.

2. Compile attendant libraries

For some strange reason, SDL_image won't find the built-in libpng. Build and install it, together with libtiff. Then, build and install SDL_image, SDL_ttf and SDL_mixer. Everything should work; if not, check that the variables above are correctly set in your session's environment.

3. Compile ocamlsdl

I assume you're using ocamlfind; if not, you'll probably not find trouble with the last step.

1. Start by doing ./configure; it should say that it'll build SDL_image, SDL_ttf and SDL_mixer.
2. Then, edit makefile.config.gcc so that lines 29 and 30 read -framework Cocoa instead of the original -Wl,-framework,Cocoa.
3. Also, edit src/Makefile so that line 89 reads $(RANLIB) $$($(OCAMLFIND) query sdl)/*.$(A) instead of the original $(RANLIB) $$($(OCAMLFIND) printconf destdir)/*.$(A).
4. Finaly make it.

If you've installed a previous version of ocamlsdl and you're using ocamlfind, you'll need to manually remove the installation directory (ocamlfind query sdl) prior to sudo make install.

3. Test ocamlsdl

I've found a great "hello world"-type of walk-through., but it needs some tweaking for MacOS X, as the ocamlsdl README explains. Use the following Makefile:

RESULT        = testsdl_1
SOURCES       = testsdl_1.ml
PACKS         = bigarray sdl
OCAMLBLDFLAGS = -custom

include OCamlMakefile

and make sure that the example built with make nc (native code) and make (bytecode) both work. Again, I assume you're using ocamlfind.

Good luck!