2008-01-28

GD on Leopard

As a once-again proud owner of a feline, I'm building my development environment. I've found an excellent walk-through for installing MySQL, and another instalation guide for GD (PDF) for PHP use. The MacBook Pro is the fastest machine I've ever used, bar none. Such a pleasure, well-worth the investment.

For the record, I'll mention the configure parameters I used to compile GD with full graphics support:

./configure --x-includes=/usr/X11/include \
  --x-libraries=/usr/X11/lib \
  --with-freetype=/usr/X11/

As in the linked-to tutorial, I assume you've installed the full X11 development libraries. With that, the result is:

** Configuration summary for gd 2.0.34:

   Support for PNG library:          yes
   Support for JPEG library:         yes
   Support for Freetype 2.x library: yes
   Support for Fontconfig library:   yes
   Support for Xpm library:          yes
   Support for pthreads:             yes

I hope somebody finds this useful.

2008-01-13

Predictor, Shmedictor

Scott Aaronson attempts to tackle the so-called Newcomb's Paradox, and discovers a new angle into it. To recapitulate quickly, the paradox poses a putative entity, the Predictor, which confronts everybody with to boxes: the first either has $1,000,000 in it or nothing, the second always contains $1,000. The catch is that the Predictor knows with perfect, inerrant foresight what your actions will be: if you choose to open only the first box, It will put the million inside it; if you choose to open both boxes, It will leave it empty. This way, you have no rational choice based on probabilistic expectations, as both alternatives of an either-or analysis contradicts the other possibility.

Aaronson's tackle on this is that the Predictor need not be omniscient, just a detailed-enough simulation of yourself that "runs" you forward enough to predict your choice and set up the boxes accordingly. Cosma Shalizi's view is that the paradox stems from trying to reason about the Predictor from the point of view of our own finiteness. I call bullshit: my view on this is that the Paradox is not, but just the result of a categorical mistake. I read the list of attempts at cracking it and cannot help but think "where's Wittgenstein when we need him?"

What I find bogus about the Paradox is the insistence to take at face value its setup in a probabilistic framework. To me it is obvious that the Predictor isn't such, but just a deterministic function from choice to payoff. Put it in these terms, it is wrong to use expectations to tackle the problem; for me, the right avenue of attack is to treat it as a maximization problem.

In other words, even if the problem poser insists on accounting for the phenomenological reality of the Predictor as defined by the problem, I can still sidestep the issue of Its nature and behave as if It does not exist as postulated. That is, it is irrelevant if the Predictor predicts my moves, as Aaronson chooses to explain, as It acts consistently independently of the chooser. Its actions are only dependent on the chooser's choice, hence, It is still a deterministic function from choice to payoff. The choice has a finite domain isomorphic to the booleans (open the second box or not):

choicepayoff
false$1,000,000
true$1,000

with maximum value at false.

Don't open that second box, silly!

2008-01-10

Pointless Polymorphism

The echo chamber started resonating with Albert Y. C. Lai's post. The point of it is that function composition is a more pervasive paradigm (or abstraction device, rather) than just higher-order functional programming. In Haskell, point-freeness is a usual stylistic device (in the literary sense); in the ML family of languages it is seldom seen.

Andreas Farre pitched in with the composition combinators defined in F#. F# shares with OCaml the syntactic quirk of arbitrary infix operators built from fixed operator characters, whose precedence and associativity are fixed in advance and depend on the first character in the operator name. For instance, in OCaml, operators starting with | are left-associative, but those starting with @ are right-associative and at a higher precedence level. I pointed out on the discussion over at reddit that this, coupled with the value restriction makes point-free style in ML-family languages (including OCaml) inconvenient.

Aside: If you don't see the point of the puns, you're not alone: I don't either, but it seems that any discussion of point-free programming induces everybody to start shooting bad puns point-blank. I'll make an effort to try and stop it.

What this means from a practical standpoint is that η-conversion doesn't quite work symmetrically: whereas f is always equivalent to fun x -> f x, the converse is not true. For example, let id x = x be the identity function, with type α → α. Then, fun x -> List.map id x has type α list → α list, but the η-converted, point-free List.map id does not: the result type in OCaml is '_a list → '_a list, where the type variables are monomorphic and unbound. The first application of this function to an argument of concrete type T will fix the point-free function's type to be TT, for ever.

I like to define the composition operator in OCaml as:

let ( % ) f g x = f (g x)

since % is relatively lightweight and it is not defined elsewhere in the standard library. The purportedly more obvious alternative would be using @, as it is reminiscent of the ring operator ∘ that usually denotes composition in Mathematics. It has two inconvenients, however: it is already in use to denote list concatenation, and it has the wrong precedence for composition, namely right-to-left.

With this, we can see that the value restriction won't let us define a point-free polymorphic reverse sort:

# let revsort = List.rev % List.sort Pervasives.compare ;;
val revsort : '_a list -> '_a list = <fun>

Even though compare is polymorphic on its arguments, the defined function is not:

# revsort [1;2;3;4] ;;
- : int list = [4; 3; 2; 1]

# revsort ;;
- : int list -> int list = <fun>

The first application of revsort to a value fixes its type to that of the value. The fix is to η-expand the function and lose point-freeness:

# let revsort x = (List.rev % List.sort Pervasives.compare) x ;;
val revsort : 'a list -> 'a list = <fun>

Here's where F# operators |> and >> are handy, as they build the composition applied to the point, in the right order (left to right). There is, however, a case where point-free programming remains applicable and expressive under a Hindley-Milner type discipline: when composing monomorphic functions.

Browsing type specimens, I came across some pangrams I didn't know. They looked like pangrams, but I didn't want to check every letter to see if they effectively were. Programming to the rescue! First, I needed to define the isomorphism between strings and lists of characters, which is built-in in Haskell but not in OCaml:

let unpack s =
  let r = ref [] in
  String.iter (fun c -> r := c :: !r) s;
  List.rev !r

let pack l =
  let b = Buffer.create 16 in
  List.iter (Buffer.add_char b) l;
  Buffer.contents b

These are imperative for efficiency, but they need not be. A predicate to test if a character is alphabetic is quite easy:

let is_alpha = function 'A' .. 'Z' | 'a' .. 'z' -> true | _ -> false

Range and or matchings are compiled very efficiently, so this is almost as good as a table lookup. Many letters will be repeated many times; the easiest way to filter duplicates is to assume that the list is sorted, and the repetitions occur in contiguous blocks:

let rec unique = function
  [] | [_] as l -> l
| x :: (y :: _ as l) -> if x = y then unique l else x :: (unique l)

The alternative would be the equivalent to Haskell's nub that removes duplicates anywhere on the list, retaining the first and respecting the order of the elements in the original list. This constitutes the generic scaffolding. For convenience, I'll alias a couple of things:

open List
open String

let sort l = List.sort Pervasives.compare l

Note that the sort is polymorphic, as it is a syntactic value (which happens to be functional). And now for the punchline, we get to the point of closing:

let letters = pack % unique % sort % filter is_alpha % unpack % lowercase

The use of monomorphic lowercase, unpack and is_alpha forces the type inferencer to derive monomorphic types for filter, sort and unique, and thus making the value restriction irrelevant here. The processing pipeline is as concisely and elegantly expressed as any in Haskell (or in Unix shell, for that matter). With that, we can test for panalphabets like this:

let is_panalphabet = (=) 26 % length % letters

For instance (à ta santé, OCaml!):

# is_panalphabet "Portez ce vieux whisky au juge blond qui fume" ;;
- : bool = true

(no diacritics were harmed in this production). Or:

# List.map is_panalphabet [
"jaded zombies acted quaintly but kept driving their oxen forward" ;
"the quick brown fox jumps over the lazy dog" ;
"pack my box with five dozen liquor jugs" ;
"sphinx of black quartz judge my vow" ;
];;
- : bool list = [true; true; true; true]

So, there is a use for point-free programming in OCaml, especially when dealing with type-based DSLs, as the functions operating on values are usually monomorphic. And this is the point I wanted to make.