Provenance semi-rings

One joy of my recent visit to Penn (see below) was a chance to look at recent work by Val Tannen and others on a generalized model of provenance. Reading these papers was the perfect way to brighten up my trip home. Truly elegant.

Todd J. Green, Grigoris Karvounarakis, Val Tannen. Provenance semirings. PODS 2007, Beijing, China.

J. Nathan Foster, Todd J. Green, Val Tannen. Annotated XML: queries and provenance. PODS 2008, Vancover, Canada.

Combining Events And Threads For Scalable Network Services

Last week, I enjoyed a visit to Penn for Nate Foster's PhD proposal. They have a great language group, and I had many enjoyable discussions. Many thanks to Nate Foster, Steve Zdanceowic, Benjamin Pierce, and everyone else for hosting my visit.

I also got to read some great papers I might otherwise have missed. Here's one, another in my next post.

Peng Li and Steve Zdancewic. Combining Events And Threads For Scalable Network Services. In Proc. 2007 ACM SIGPLAN Conference on Programming Languages Design and Implementation (PLDI), pages 189-199, 2007.

Mandelbrot Maps

My MSc student, Iain Parris, has put together a brilliant web-based app for viewing Mandelbrot and Julia curves in real time. It lets you move about a point on the Mandelbrot set, and displays the corresponding Julia curve in real-time. There are other apps that perform similarly, but this is the only one I've seen that provides real-time response. Try it out!

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.