Caml Trading

Caml trading – experiences with functional programming on Wall Street
by Yaron Minsky and Stephen Weeks
Journal of Functional Programming, Volume 18, Issue 04, July 2008, pp 553-564

Functional programmers are always keen to gather evidence that it is actually of use in the 'real world'. Jane Street Capital, by adopting O'Caml as the language in which they write the programs that earn them so much money, has provided one of the clearest demonstations. Yaron Minsky delivered a brilliant invited talk to this effect at POPL 2008, and I'm delighted to see that he and Steven Weeks have now published a companion article for JFP.

An error in a financial program of this kind can wipe out a firm's profits for the year in a few seconds, so reliability is a concern. The partners of Jane Street review the code themselves, and this turned out to be one of the major factors influencing the adoption of Caml.

I thought their comments on OO programming were of interest.

When we first tried switching over from VB to C#, one of the most disturbing features of the language for the partners who read the code was inheritance. They found it difficult to figure out which implementation of a given method was being invoked from a given call point, and therefore, difficult to reason about the code. It is worth mentioning that OCaml actually does support inheritance as part of its object system. That said, objects are an obscure part of the language, and inheritance even more so. At Jane Street, we almost never use objects and never use inheritance. We use standard functional programming techniques and code reviewers find that style more comprehensible. In particular, they can reason by following static properties of the code (module boundaries and functor
applications) rather than dynamic properties (what class an object is).

I've had similar thoughts about the perils of inheritance, but this is one of the few places I've seen them documented.

Welcome to Scotland, Neil, Patricia, and Conor!

A big welcome to Neil Ghani, Patricia Johann, and Conor McBride, who are establishing a new research group in Mathematically Structured Programming at the University of Strathclyde. And a big congratulations to Strathclyde, on attracting three top-notch researchers. Their arrival will strengthen the already strong programming languages community in Scotland, and they've already volunteered to host a meeting of SPLS.

Add FP to the ACM curriculum

As a result of a recent Harvard workshop, there is a proposal to add FP to the ACM curriculum, and ACM members are encouraged to comment. Many excellent arguments appear on the comment page, here are two of my favorites.

Greg Morrisett:

I strongly endorse the recommendation to include functional programming in the curriculum. The most important benefit is a change in the mode of thought that can strongly influence design at all levels, from hardware to distributed systems. If they are to be successful, students must be able to pick up and learn new languages. Without deep experience in at least two very different environments, they will be unable to do so.

Robert Harper:

I endorse the proposed change to PL7/FunctionalProgramming to include more hours on the topic of functional programming and to correspondingly reduce commitment to vague or obsolete topics in the proposed curriculum. Functional programming has emerged as the central organizing principle in programming language design, and is increasingly important in industrial as well as academic settings. Once considered an esoteric niche topic, functional programming has emerged as a unifying conceptual framework that encompasses and enriches traditional concepts such as imperative and object-oriented programming. Many of the major innovations in language design over the last decade have emerged from the functional programming perspective, including reliance on managed storage ("garbage collection"); emphasis on static type disciplines in general and specific advances such as generics in particular; and the role of higher-order techniques, including functions and objects, for building reusable software component.

Current trends in the computer industry favor the functional perspective: (a) very large scale distributed computing models, such as Hadoop or map/reduce, depend essentially on the functional (state-free) model of computing; (b) small to medium-scale parallel computing, such as multicore processors or shared memory multiprocessors, strongly favors the functional model, which ensures determinacy of outcomes even in the presence of parallelism; (c) demand for mechanical verification of program properties to ensure software quality favors the functional model, which emphasizes the single most successful integration of formal methods into programming, rich static type systems.

It is entirely appropriate for ACM to place renewed emphasis on functional programming in the undergraduate curriculum. The present proposal, though overly modest, takes a step towards modernizing undergraduate education in programming languages. I urge that this change be adopted.

History of Lambda-calculus and Combinatory Logic

This is the most definitive history of lambda calculus of which I am aware, a most useful resource. It includes two contradictory stories, both told by Church, of why Church picked the symbol 'lambda' (see p 7), but not the story that Church conceived the predecessor function after exposure to laughing gas at his dentist. (Does anyone know a source for that story?) My thanks to the authors for their efforts.

The Expression Lemma

Ralf Laemmel and Ondrej Rypacek have a paper in MPC 2008 on the duality of functions and objects, which they formalize as folds over algebras and unfolds over coalgebras, as a step toward deeper understanding of The Expression Problem. I like their idea of dual models of functions and objects as algebras and coalgebras, has this appeared elsewhere?

Alien Category Theory

From Glory, by Greg Egan, a story about one alien race trying to uncover the mathematics of another alien race, three million years old.

The theorem itself was expressed as a commuting hypercube, one of the Niah's favorite forms. You could think of a square with four different sets of mathematical objects associated with each of its corners, and a way of mapping one set into another associated with each edge of the square. If the maps commuted, then going across the top of the square, then down, had exactly the same effect as going down the left edge of
the square, then across: either way, you mapped each element from the top-left set into the same element of the bottom-right set. A similar kind of result might hold for sets and maps that could naturally be placed at the corners and edges of a cube, or a hypercube of any dimension. It was also possible for the square faces in these structures to stand for relationships that held between the maps between sets, and for cubes to describe relationships between those relationships, and so on.

That a theorem took this form didn't guarantee its importance; it was easy to cook up trivial examples of sets and maps that commuted. The Niah didn't carve trivia into their timeless ceramic, though, and this theorem was no exception. The seven-dimensional commuting hypercube established a dazzlingly elegant correspondence between seven distinct, major branches of Niah mathematics, intertwining their most important concepts into a unified whole. It was a result Joan had never seen before: no mathematician anywhere in the Amalgam, or in any ancestral culture she had studied, had reached the same insight.

Fun with correlation and citations

I'm sure I'll want to cite this someday, possibly in class but perhaps in the pub. What I'll be citing it as an example of, I'm not yet sure. Thanks to Leonid Libkin for spotting this.

Fractal Food

Who can resist
Sierpinski cookies and fractal pizza? Spotted via Boing Boing.

AOSD 2008, Brussels

Last week I delivered a keynote at AOSD, on Well-typed programs can't be blamed. It was a marvelous opportunity to learn more about aspects, and more about Brussels.

The photo shows me with Gary Leavens atop the Musical Instruments Museum. You wander around wearing a headset, and when you stand next to an instrument you can hear it play. Someday soon, our whole world will be augmented in this way; but you won't need a specially supplied headset, you'll use your phone. One pleasure of my trip was to meet Wolfgang De Meuter and Tom Van Cutsem, whose Ambient Oriented Programming is aimed at just such applications.

People I enjoyed meeting include Dean Wampler, Eric Eide, Curt Clifton,
Emilia Katz, Maja D'Hondt, and Ellie D'Hondt. Ellie works in quantum computation, and told me (rather to my surprise) that monads have an application there. She had once read one of my papers on monads, but found it too difficult. This cheered me up, since I feel the same when I try to read about quantum computation.

Special thanks to Theo D'Hondt, Viviane Jonckers, and Isabelle Michiels for organizing the conference so well.

Functional Programming is Beautiful

If you use Lisp and disdain Haskell, or vice versa, you'll want to read this brilliant Orwellian strip by Conrad Barski. Spotted by Ehud Lamm at Lambda the Ultimate. Thanks Conrad! Thanks Ehud!