Package interfaces

So we all know that you should program to an interface, not an implementation, if you're writing a program in the modular, component-oriented world. In Java or ML, at a basic level this is pretty much straightforward to do: you get some object with a known interface (or you import some structure with a known signature) and start referring to its fields/methods/values/types however you'd want, by saying some variant of "I want resource x from component C" every time you want something. Every time you want something from a component, you write down what you want, and from which component you want it. If you name something that you don't know to exist, the compiler yells at you and that's the end of the story. If the maintainer of the component you're using adds a new resource to the interface tomorrow, that doesn't affect your code at all.

In PLT Scheme the situation is a bit worse. When you import a module, you just name it and all its provided names get dumped into your namespace. If you import two modules, they must have completely distinct namespaces, or mzscheme doesn't know which one you wanted and signals an error. This has an insidious effect that becomes apparent as programs evolve: if you import a module, you're not only relying on it providing some names, but also on it not providing any other names. That means that if you start using somebody else's component and that person adds a new resource to its interface, your code might break.

This problem has always existed, but PLaneT turned it from a hypothetical problem to a real one. It has a tendency to do that ...

MSPLS

On Saturday I went down to lovely Champaign-Urbana and gave my Earthlings and Martians talk at the annual meeting of the Midwest Society for Programming Languages and Systems (MSPLS). It was the second time I've given this particular talk to a reasonably-sized audience (or third, if you count the impromptu delivery I gave to the PL Lunch crowd on Friday) and I think it went about as well as before.

Well, as well as before but with one pretty important twist: the folks down at UIUC have been interested in using term rewriting to give semantics to programming languages, and they've been actively studying the potential there for a few years. They've grown a particular term-rewriting style out of the standard formal systems in use by the term-rewriting community that they argue is particularly good for giving semantics to programming languages; as we were watching each others' talks it struck both me and them that what they've got is very similar to Felleisen-Hieb-style context-sensitive reduction semantics. Since I go down to Champaign-Urbana all the time anyway, they suggested that I stop by the computer science department one day so we could get together and teach each other what we're doing.

So we're doing that next Monday. I'll give them a tutorial on context-sensitive reduction semantics and PLT Redex, and maybe they'll be able to teach me their particular brand of rewriting semantics and all the neat tools they've been developing there. Neat!

A personal tragedy of epically minor proportions

As I was making coffee this morning, I dropped my trusty Ozaukee Bank mug and broke it. It's the mug that I've had with me all through graduate school. It's been with me for every paper I've written here and it's probably directly responsible for every one of the ideas behind those papers. Ozaukee Bank mug, you will be missed.

As a side note, I'd like to thank whoever it is who had the original idea for coffee. You have put forward the cause of science by hundreds of years.

ICFP 2006

Paper: submitted. This is the multi-language semantics paper I've been working on forever; the one that was going to be an ICFP '05 paper, then a POPL '06 paper, and then an ESOP paper, but we never ended up submitting to any of those places because it wasn't ever finished. Now it's finally finished, so there's nothing left to do but hope.

It's called "The Meaning of Multi-Language Programs" and it's by me and Robby Findler. Here's the abstract:

Interoperability is big business, a fact to which .NET, the JVM, and COM can attest. Language designers are well aware of this, and they are designing programming languages that reflect it --- SML#, Mondrian, and Scala all treat interoperability as a central design feature, just to name a few. Still, current multi-language research tends not to focus on these languages' semantics, but only on how to implement them efficiently. In this paper, we attempt to rectify that by giving a technique for modeling a multi-language system as a composition of the models of its constituent languages. Our technique abstracts away the low-level details of interoperability like garbage collection and representation coherence, and lets us focus on semantic properties like type-safety and termination behavior.

We demonstrate the technique with a series of strategies for embedding a Scheme-like language into an ML-like language. We will start by connecting very simple languages with a very simple strategy, and work our way up to languages with sophisticated features like effects and that interact in sophisticated ways. Along the way, we prove type-soundness for each system we present. Our technique allows these proofs to be straightforward generalizations of standard type-soundness proofs for single languages.

Beyond giving simple expressive models, our studies have uncovered several interesting facts about interoperability. For example, higher-order function contracts naturally emerge as the glue to ensure that interoperating languages respect each other's type systems. Our models also predict that the embedding strategy where foreign values are opaque is as expressive as the embedding strategy where foreign values are translated to corresponding values in the other language, and we were able to experimentally verify this behavior using PLT Scheme's foreign function interface.

Once I'm ready to put the full paper online I'll post a link.

ICFP Contest 2006

As you may recall, last year I was involved in organizing the 2005 ICFP Programming Contest. Well, mark your calendars, because I just discovered by random googling that our successors at Carnegie Mellon have put up a web page for the 2006 contest, and they've even announced the dates on which it will be held: July 21 through 24.

I'm really interested in seeing what the CMU folks will come up with. I don't have any insider knowledge, just a slightly higher-than-average interest in the subject, but I'd guess they're planning something quite a bit different from the contests of recent years. Recently the contests have been essentially about writing game-playing agents; I'd bet they're going to go back to something a little more abstract.

A few off-topic topics

I saw that the great science-fiction writer Stanislaw Lem died this morning at the age of 84. Lem is probably best known for writing Solaris, which was adapted into a movie in 1972 by Tarkovsky and again in 2002 by Steven Soderbergh (starring George Clooney), but he's got a great many great novels to his name. I've only read five or six, but I've enjoyed every one I've read — in particular I think The Cyberiad might be my favorite book of any genre at all.

In happier news, congratulations to my dad, John Matthews, who on Friday became Dr. John Matthews when he successfully defended his dissertation on public policy. Dad worked for various city and county governments for many years, then took an early retirement and went back to school to get his PhD. Just think, he gave me a gigantic head start and still finished his PhD before I did! Oh well. Congratulations to him.

Quartz Composer: the world's most widely-used functional-reactive programming language

A couple days ago, Apple held a "Technology Update Briefing" here at University of Chicago. A "Technology Update Briefing," as it turns out, is where they send a developer around to demo all the cool new developer toys they've hidden away in Tiger, mostly in the XCode package you installed because you wanted GCC.

Our developer, Steve Hayman, pointed out a bunch of neat toys. He started out by pointing out a couple things I'm sure most developers who use Macs already know: for one thing, OS X has Unix inside and so you can use pipes if you want; and for another, the new Automator tool is a lot like a GUI's notion of piping (the robot is actually holding a pipe in reference to that). So far the talk was entertaining but didn't tell me anything I didn't already know.

But the next thing he pointed out was really new and totally cool: Quartz Composer. Quartz Composer is an application that comes with XCode on Tiger, so you've probably already got it installed (I did, anyway). What it does is allow you to build QuickTime objects, like movies and so on, by gluing together "patches" to create a pipeline, purely declaratively. Of course as far as Apple is concerned, it's a "visual programming environment" where you make graphical programs "without writing a single line of code", but of course that's not really where the sysmem's power comes from — you don't type in a single line of code, but as far as I'm concerned drawing lines between boxes on the screen and the other visual manipulation you do is just an incidental difference.

The real power of Quartz Composer is that it's purely declarative. If you want a bouncing ball, you don't write a loop that update's the ball's Y-coordinate once every however-many fractions of a second; you attach the ball's Y-coordinate input to the output of a low-frequency oscillator whose value depends on the time. If you want this morning's headlines from the BBC to show up on the screen, you make a text displayer and attach its text input to the output of an RSS feed monitor. If you want that text to follow your mouse around the screen, you attach its X- and Y-coordinates to monitors of your mouse's X and Y positions.

They never say it, but what they've implemented is functional-reactive programming, and by virtue of the fact that it's shipped with Tiger I'm willing to bet that it's the world's most widely-used FRP implementation. Furthermore, the Quartz Composer programs you can find online (for instance here) demonstrate that the approach scales way up.