Keep Working, Worker Bee!

Package interfaces

2006-05-10T19:45:00.000-05:00

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

2006-04-25T09:14:00.000-05:00

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

2006-04-14T10:09:00.000-05:00

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

2006-04-07T20:13:00.000-05:00

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

2006-04-05T13:47:00.000-05:00

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

2006-03-27T16:24:00.000-06:00

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

2006-03-23T09:18:00.000-06:00

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.

Scheme semantics in Maude

2006-03-18T10:55:00.000-06:00

I just stumbled on some work that's related to the R5RS operational semantics paper I wrote recently. Right at about the same time I was doing that, some folks on the Maude team did a Maude-based rewriting semantics for Scheme also, and wrote a paper about it for the Brazilian Symposium on Programming Languages called "An Equational Specification for the Scheme Language" (source code). It looks like they didn't model the two things that gave me the most trouble (unspecified order-of-evaluation and multiple values). Also, they're excited about the fact that their model of call/cc is so small, but that's because their entire system is in CPS style ...

Anyway, it's interesting to compare their system to ours and see how our different priorities led to different systems. For instance they've got an entire section on performance metrics. Performance was explicitly a non-goal for us. If our paper had a section on performance, it would read something like: "We were able to compute (fib 7) in, like, an hour or so."

Olin Shivers' SRE notation

2006-03-16T23:14:00.000-06:00

I just got pointed at Olin Shivers' SRE regular-expression notation design document. Not only is it a really neat, elegantly-designed library that I'm a little surprised we haven't all adopted yet, but it's also got a pretty great preamble that's worth reading just by itself.

... [L]et's take the case of someone who wants to do web hacking in Scheme. His Scheme system doesn't have a sockets interface, so he sits down and hacks one up for his particular Scheme implementation. Now, socket API's are not what this programmer is interested in ... So he does a quick 80% job, which is adequate to get him up and running, and then he's on to his orignal goal.

Unfortunately, his quickly-built socket interface isn't general. It just covers the bits this particular hacker needed for his applications. So the next guy that comes along and needs a socket interface ... does his *own* 80% implementation. Five hackers later, five different, incompatible, ungeneral implementations had been built. No one can use each others code.

The alternate way systems like this end up going over a cliff is that the initial 80% system gets patched over and over again by subsequent hackers, and what results is 80% bandaids and 20% structured code. When systems evolve organically, it's unsuprising and unavoidable that what one ends up with is a horrible design -- consider the DOS -> Win95 path.

I'm a Rejected Scientist

2006-03-15T11:34:00.000-06:00

That was fast. We just heard back on the paper we wrote for Science that I mentioned last week; REJECTED! Not a big surprise at all, of course. Would've been nice, though ...

More on polymorphic contracts

2006-03-14T23:49:00.000-06:00

It's remarkable how fragile some results of type theory can be. Last time I wrote about polymorphic contracts, I offhandedly mentioned that in an ML-like language a function of type ∀α.α→α might memorize the first argument that it is provided with at runtime and thereafter always return that value. I was actually thinking of a full System F + state language; I'm pretty sure that it isn't possible to write a function that behaves that way in actual SML. Surprisingly, though, you can get a polymorphic memory function if you're willing to relax the type to ∀α.unit→α→α. Here it is:


let val (f : unit -> 'a -> 'a) =
     fn _ =>
      let val memory = ref NONE in
       fn x =>
          case !memory of
       NONE => (memory := (SOME x); x)
            | (SOME y) => y
      end
    val g'  = f()
    val g'' = f()
in
    (g' 1, g' 2, g'' "hello", g'' "goodbye")
end

This program typechecks in SML and produces the value (1,1,"hello","hello").

So what's going on here? It doesn't seem like taking an additional unit value should affect anything, but clearly it does. Here's why: when you apply a polymorphic function in ML, you're actually doing two things: first, you're supplying the function a value argument, and second, you're implicitly supplying it with concrete types for all its type variables. (You have to do both of these at the same time because of SML's value restriction.) So, if you're writing a function of type ∀α.α→α, then every time you call it with a new value, you're also calling it with a new type. If you have one piece of memory for all of these calls, then you might remember an argument of type α when α = int and then return it when α=string, which would violate ML's safety guarantee.

Now instead let's say you're writing a function with type ∀α.unit→α→α. Now when you call the function for the first time, you're supplying it with the trivial unit value and also a particular choice for α. Now, in the body of that function you can set a cell of memory that only holds values of that particular choice for α, and then a function that consumes and produces a value for that same choice of α. In essence, that first unit argument is just there to hack around the value restriction; it gives us a way to do some computation in between picking the particular type we want to use for α and coughing up a function that consumes and produces αs.

So, what does this have to do with polymorphic contracts? Well, I've got a prototype polymorphic contract implementation working, and this exact issue pops back up but in a form that's a little more annoying. In order to be able to write down ML functions like the one I've posted here and have them typecheck, you pretty much need to understand ML's type system. You simply can't execute a program that doesn't work. Polymorphic contracts, on the other hand — it's easy to write down a program using polymorphic contracts that will definitely cause a contract violation in the right contexts (like if you write a memory function and give it contract ∀α.α→α) and then execute that program, maybe even succeed on lots of inputs, without noticing you've done anything wrong.

More about speed-dating

2006-03-11T19:08:00.000-06:00

I'm not sure if I mentioned this before, but the Science paper I mentioned a few days ago isn't the first speed-dating paper I've been involved in. The first was a paper on how to run a speed-dating event for the purpose of studying interpersonal relationships; Eli Finkel, Paul Eastwick and I submitted it to a psychology journal in December.

Today we heard back about it. The editor sent us a very encouraging letter that asked us to revise and resubmit it. Furthermore, the four anonymous reviewers seemed to really really like it, though of course they each had something big they wanted changed. All in all, it hasn't been accepted yet but it's a pretty sure bet that it will be after a round or two of edits. Yay!

I'm a Scientist

2006-03-09T23:17:00.000-06:00

As of today, I may officially call myself a Scientist, by the very technical and totally non-common-use definition that I have a paper submitted to the journal Science. It's not about computer science at all; it's about speed-dating. Anyway, as of a couple days from now I'll be able to call myself a Rejected Scientist, but it's fun for now.

Polymorphic contracts

2006-03-07T17:16:00.000-06:00

What does it mean for a the ML or Haskell type checker to give your function the type ∀α.α→α? It means that even though you haven't told the compiler what type T you're thinking of, it can prove that your function has type T→T anyway. After a moment's reflection you realize (and after a huge pile of math you can prove) that the only way the type checker could do that is if your function has all of those types simultaneously, so it (a) doesn't do anything to its argument and (b) returns that argument intact. Or maybe it diverges on all inputs, or maybe it remembers prior values it's been given and returns one of those or something like that, but it never makes up new values and returns those.

So, what does it mean if you give a Scheme function the contract ∀α.α→α? One interpretation is that you're asserting that your function satisfies all of the contracts C→C for every C simultaneously. There's only one way you can say that; it's if your function returns its argument intact, or diverges on all inputs, or returns a previously-remembered input value. (That's easy enough to show based on the view of contracts as pairs of projections, incidentally.) It may make first-order observations about its argument, but it cannot do anything to it that would assume any particular contract on it, like seeing that it's a procedure and calling it with an argument. If you do, it's a contract violation because whatever you do there's some contract that your use would be violating. That system almost already implemented in the current PLT Scheme contract library, in the form of anaphoric contracts.

There's another way to do it, too, though, based on a different interpretation. We could also interpret the contract ∀α.α→α to mean, "for any contract C you give me, I can give you back a function that satisfies the contract C→C." In this interpretation, contracts aren't analagous to for-all types, they're analagous to kinds in the sense of System F_ω. In this system, a function gets to know the contract it's expected to conform to, and it might be able to take special action based on that knowledge. It's more powerful, but also more difficult to use: your function has to explicitly take in a contract, and anywhere you use it you've got to tell it the contract you're thinking of. Furthermore, it's not really a "contract" anymore, since it's not a projection on values directly; it's more a "contract kind."

This system is technically already possible in the PLT Scheme contract system: (->d contract? (lambda (c) (-> c c))) is the contract kind that produces C→C contracts.

[Edit 3.08.06 9:34: "Anaphoric", not "anamorphic" (nor "Anamorphic", and definitely not "Animorphic"). Thanks Dave!]

electronic music in Scheme with impromptu

2006-03-04T10:49:00.000-06:00

Here's a neat project that got mentioned over the plt-scheme mailing list at some point: impromptu, a Scheme/OSX-based electronic music environment. I've been casually interested music-specific programming languages for a while, but up until now the best thing I'd found was CSound which doesn't thrill me.

My main reason for being interested is that I think music could be a very natural way to teach students about higher-order functions: a sound is a function from time to frequency, and all sound operations become function composition. Want to make a 5-second sound clip last 10 seconds instead? It's a one-liner. Want to shift the pitch up or down? Just as easy. Want to do both? No problem. I think it's a really natural way to think about sound that leads just as naturally to higher-order functions, and that's pretty cool. It's also the sort of thing I can imagine one or two kids really nerding out over, which is definitely a bonus.

You may not like Tait's Method, but you've got to admit ...

2006-03-04T00:50:00.000-06:00

It seems like everything I'm learning these days is coming from unpublished books. For a long time I was reading stuff from Felleisen and Flatt's Programming Languages and Lambda Calculi (google for it); from it I got a foothold on contextual equivalence after quite a bit of struggling. Then, more recently, I discovered Bob Harper's Type Systems for Programming Languages (available from his homepage), which has a great amount of good material and also talks about contextual equivalence in a totally different way from Felleisen and Flatt. (For instance see his discussion of "ciu-equivalence".)

Anyway. Sorry for the lack of updates. Strangely, the more I'm doing the less I can write about, and I've been very busy lately. I've been doing a tremendous amount on my multi-language semantics project recently and I'd love to talk about all of it, but unfortunately all of it is a bit too fresh for me to talk about it here.

What I can do, though, is take this opportunity to publicly praise Derek Dreyer's advanced type theory class for directly helping the research I'm working on now. Derek's class is the first class in which I had to understand the proof that the simply-typed lambda-calculus terminates; I learned how to do that proof about six weeks ago, and this afternoon I adapted it to complete the proof of a very surprising multi-language systems result. Imagine that! Things that I learn in school being relevant to research!

Congratulations, Dave!

2006-02-20T20:26:00.000-06:00

I guess now that Brendan Eich has announced it, it's official: Dave Herman is working with the committee for a new version of JavaScript. Congratulations, Dave! I don't know, but I'd guess that these excellent posts he made may have had something to do with it ...

PLaneT improvements

2006-01-24T23:13:00.000-06:00

I've been working a lot on PLaneT, and I'll be doing more in the coming days and weeks. A summary of what I've been up to in that regard:

The PLaneT client now support "development" links between PLaneT require specs and arbitrary directories on your file system, intended to make PLaneT package development easier
The PLaneT server now allows packages to specify a minimum mzscheme version that they should be installed on
Several improved error messages
A couple bugfixes that would have caused the client to crash the wrong way on certain errors
MIME-type tweaks on the server
The server is now running the latest SVN version of PLT Scheme. The primary reason for that was to get the client code synched up with the server code, but it may also have the effect of improving server stability

There's more coming up, by the way. I'm glad to see that people are using PLaneT for stuff.

What They Don't Teach You In Graduate School

2006-01-24T10:51:00.000-06:00

I recently heard about a series of articles from Inside Higher Ed called "What They Don't Teach You in Graduate School" that look pretty interesting:

Part 1 — finishing your dissertation and finding a first job
Part 2 — your academic responsibilities
Part 3 — the tenure track
Part 4 — your life as an academic

The most useful thing I've done with TeX so far

2006-01-19T20:05:00.000-06:00

is this:

I've come to face the fact that (a) I really never learned more than the "greatest hits" of the Greek alphabet, and (b) not knowing my phis from my zetas will actually hinder my academic progress at this stage of the game. So, a cheat sheet.

POPL and PLaneT and type theory

2006-01-17T20:49:00.000-06:00

Hi all, and apologies for the lack of updates; unfortunately I've been busy and haven't really had much time to tell you all what I've been up to. Anyway, over last week I was in sunny Charleston, South Carolina for POPL 2006. It was pretty great; I've got some notes, but unfortunately I don't have time right now to type them all up so I'll save that for another day. I will point you to "Environment Analysis via ΔCFA", a pretty crazy and interesting extension of Olin Shivers' CFA technique by Matthew Might and Shivers himself. I award it high marks even though it does use "via" in the title (yes, I'm aware I've done the same thing, but now I'm embarassed about it).

While I was there, though, I did manage to pick up a copy of The Reasoned Schemer, and I even got it signed by Will Byrd. (Sadly, Dan Friedman left before I got the book, and Oleg wasn't there at all as far as I could tell.) I haven't worked through very much of it yet, but what I've read so far has been fantastic. Very much in keeping with the other Schemer books, it's whimsical but fathoms deep at the same time. Great stuff, I can't wait to work through the whole thing.

Also while I was there I managed to advertise PLaneT around to all the Schemers there who hadn't heard of it. Self-promotion is pretty awkward for me, but it really surprised me to see how many people who were knowledgable about Scheme and even PLT Scheme who didn't know what it was. I think I need to figure out a better way to get people to know it exists; particularly for a tool like PLaneT it's really important that everyone know about it.

Speaking of PLaneT, I've been working on it recently; I just put out some improvements and I expect there'll be more before too long. Right now the user story is pretty good, but the developer story is lacking; there are lots of tiny little gotchas that aren't a big deal if you know what's going on but are pretty unfriendly to people who don't. Some particular examples that have happened in practice: developers not realizing that planet requires aren't like lib requires; developers writing code whose compiled form cannot be written to file; developers not realizing that planet package version numbers are different from their own provided version numbers; developers making packaging errors because they develop things as a collection and release it as a planet package; and so on. I'd rather have these problems never arise than to be able to smugly point out to the authors of broken packages that they should've read the documentation more carefully.

One more thing, a really surprisingly fun and frustrating puzzle from a type theory class I'm taking: assume you've got the simply-typed λ-calculus with base type T, but no constants that have that type. Prove that there are no terms at all of type T. Once you've done that, for more fun, add the special expression Omega with type T -> T and evaluation rule Omega --> Omega and prove the same thing again. It seems completely obvious, but I found proving it frustratingly difficult.

Ruby on Rails, macros, and code generation

2005-12-23T00:13:00.000-06:00

Now that the quarter is over and my paper is submitted, I've had a little bit more breathing room and one of the things I've been doing is looking into Ruby on Rails. I can hardly say I'm a Rails expert after the few hours I've spent tinkering with it, but one thing about it really struck me: Rails does an awful lot of code generating for you. One of the first things they tell you to do in the beginners' tutorial is to run a battery of scripts that generate several ruby files in several different directories, all of which are generated pretty much systematically but have some minor variation based on the particulars of your application.

Of course my immediate Schemey reaction was to think that they had yet again confirmed that those without macro systems are doomed to reinvent them (probably poorly). But delving into it a little more, I'm not so sure I was right about that. I more-or-less randomly came across a blog post by David Hansson about why he thinks Rails deserves to be held in higher esteem than your average code-generation wizards. His basic argument is: Rails code generators are just creating stubs, not any real code; but they're creating the right stubs. New subclasses derive from the right base classes, even though they don't have methods. They're put in the right directories, and give you a good factoring from the beginning. He doesn't view it as a panacea, but he does think it's useful.

In essence, if I understand the argument correctly the RoR scripts aren't there to take away the drudgery of writing repetitive code so much as to be executable documentation on proper Rails use. That sounds like a much more intriguing idea to me.

Paper submitted

2005-12-17T10:52:00.000-06:00

Well, it was looking a little unlikely at the end, but I'm happy to report that The Ins and Outs of type dynamic and Fine-Grained Interoperability by Matthews, Findler, Gray, and Flatt has been submitted. The name is actually a double meaning. One thing about working on a paper with Robby and Matthew is that if you come up with a dumb pun for the name of something, they will insist that it stay in — these are the guys who named MrEd, after all :).

This marks the first time I've submitted anything that includes my interoperability work. Exciting!

Anyway, I'm about to head out, so if I don't get back to you before then, I wish you all a very happy holiday!

[Yes, that was just for Bill O'Reilly's benefit.]

Summing up computer science

2005-12-05T22:15:00.000-06:00

So I've been pretty busy working on an ECOOP paper recently — more about after it's actually done — but I thought I'd report on my class, now that I've done all the lectures and I'm just waiting for people's final projects. I got through all the material I had wanted to cover with a spare lecture to go, so I made a lecture that I've wanted to do for a long time: build up all of computer science from transistors all the way up to the Halting Problem.

I had an hour and a half to get through that, so obviously I had to, err, summarize large portions of that material, but I still covered some of my favorite topics in a fair amount of detail. I showed how you'd build a NAND gate out of transistors (skipping the messy electrical bits like resistance because I'm an electricity imbecile), then built up NOT, AND, OR, and XOR from that, and from there did latches and briefly touched on clocks and timing. From there we quickly got to compilers and operating systems (both of which were just glanced upon), and from there applications like networking and databases.

After that I pointed out there are a lot of things that are the same between all these areas, and that database writers and operating systems writers and so on shouldn't have to independently figure out how fast their algorithms are or how to verify they work. That let me start talking about algorithms and big-Oh notation. From there you can ask whether there are any problems that require a certain amount of time, and that let me skim the proof that it takes big-theta(n*log n) to sort a list of numbers given only a comparison function. From there I was able to explain P vs. NP (though I think I sort of botched this part) and then ask whether there might be programs that you can't solve at all, no matter how much time you had. That led me to the Halting Problem, and that's where I left it.

I think these sorts of big-picture lectures are really important to an intro class, particularly when it's about a subject like computer science where the discipline isn't obvious to outsiders. I'm sure the students only got a very superficial understanding of the subjects I was talking about, but that's what the rest of the major is for.

What's wrong with computer science?

2005-11-19T09:42:00.000-06:00

At U of C, computer science is a part of the Physical Sciences Division (along with math; hey, I don't make the org charts). It turns out that twice a year, a committee comprising about thirty business and academic leaders from around the country and the world comes in to visit; the PSD puts on several presentations saying what it's doing and what it plans to do, and the committee gives it advice. The most recent meeting of this committee was yesterday, and as part of it I was asked to be on a discussion panel about my research experience.

I told them about PLaneT; I told them about the Freshman Dating Study (which incidentally just had some of its results published in a journal paper); I told them about going to Estonia and Aachen and so on. It was fun. After I and the rest of the panel had given our little introductions, the visiting committee asked us questions for about an hour. Most of them were about being a woman in the sciences, which I'm not really very qualified to answer, but I did get asked one really good question: what, a committee member asked me, was the worst part of the computer science department?

I had to take a second to think about that. What I ended up saying was that there is a tremendous amount of need in all the sciences for the expertise we've got, and we're letting a lot of it go unmet. We actually do a lot of outreach — the scientific computing people, the computational linguistics people, the whole bioinformatics group — but these efforts are drops in the bucket. Everyone in every scientific discipline needs to know enough about programming to make computers work for them, and we in computer science could be making sure that all those people learn how to do things the right way. As it is they learn from each other, which sounds to me like a recipe for propagating suboptimal programming techniques and depending on old and bad technologies.

2005-11-14T09:49:00.000-06:00

Bruce Tate's Technologies to Watch article at O'Reilly's OnJava site points out four new technologies that he says may threaten Java's dominance. They are:

Dynamic Languages
Continuation Servers
Convention Over Configuration
Metaprogramming

Interesting ... Scheme has been at the center of three of these four new technologies since their beginnings.

2005-11-08T10:29:00.000-06:00

Are disjoint unions a lurking horror of typed programming languages?

I've been reading about the XDuce project recently for our PL reading group here at Chicago. XDuce is a domain-specific language for writing XML transformations in a totally type-safe way: not only do XML values need to match their schemas, but your program needs to respect that schema too. For instance, if you're writing a program to process XML documents that look like

<A><B>[some string]</B><B>[some other string]</B> ...</A>

then the type system won't let you try to select a tag named <C>...<C> out of it.

To make that happen, XDuce introduces a really neat idea called regular-expression types. Regular expression types are just what they sound like: in addition to ground types like string, you also get sequencing, Kleene-star, alternation, and so on. (Also, because it's XML, you get "tag types": A[ty] is a tag named A whose contents have the given type ty.) So a possible type for the XML documents above might be A[B[string]*]. Pretty cool. But the really cool part is that they define the subtyping relation to be the same as the subset relation: each type describes a set of trees, and if you have two types t₁ and t₂, and t₁ describes a strict subset of t₂ then t₁ <: t₂. For instance,

A[B[string],B[string],B[string]] <: A[B[string]*]

and

A[B[string]*] <: A[any]

This is given in the XDuce literature purely as a way of making a type system that would work with XML data, and I think it's obviously useful for that purpose. During our discussion, though, the reading group started speculating as to whether it would be useful for general programming too. The MLians in the group (i.e. everyone but me) argued that it wouldn't be, since ML's tagged union types give you the same power in a more organized way.

That got me thinking: at the most fundamental level, how is this system different from ML's normal system? I think the answer is, ML forces all unions to be completely disjoint. You can say

datatype myunion = A of int | B of int

but any value of type myunion can only ever be one of the two possibilities, not both simultaneously. At its core, I think XDuce's regular expression types don't force that on you: you might well have a single value that is an instance of both alternatives in a union type, and that's where both the power and the complication come in.

So here's what I'm wondering now. When programming in ML, I've never actively noticed myself contorting programs so that I can make a particular union type disjoint when it wouldn't naturally be that way, but is that just because I've never thought of that as an option? Are lots of ML programs more complicated than they ought to be because of this restriction?

I think every language has its set of "lurking horrors," limitations or design decisions that force you to write particular programs in unnatural ways. I call them "lurking" because you don't necessarily realize you're being limited while you're coding; usually you've got to have some sort of epiphany, like learning a new language that doesn't have the same restriction, to realize that you've been tied up the whole time. Lack of higher-order functions is a big example of a lurking horror; type systems without polymorphism or option types are another. Are disjoint unions a third?

2005-11-02T09:56:00.000-06:00

Between his talk here at U of C and his invited talk at ICFP this year, Bob Harper has convinced me I ought to look into Twelf: even us "regular folks" who aren't interested making up logics and seeing what neat theorems a program can deduce unaided (ivory tower!) but instead just want to prove regular old theorems about properties of programming languages (practically blue-collar!) can derive benefit from it. So I went to the web site, downloaded and installed the software and started in on Andrew Appel's tutorial.

First impression: cool! I'm not at all skilled at it yet — I've been able to prove that (A or B) implies (B or A), (A implies B implies C) implies ((A and B) implies C) and similar teensy little logical theorems but nothing bigger. Nonetheless, when I'm writing theorems in Twelf I feel like I'm in a cool place where I'm doing programming (easy!) but the result is math (hard!). Of course that's not really fair, since the programming is very mathematical and the proofs very easy; we'll see how I feel when I get to the point where I'm using it to prove type-soundness theorems and the like.

(Oh, and note to the myriad Twelf implementors that undoubtedly read this page regularly: the README doesn't tell you that if you've only got SML/NJ installed you've got to say ./smlnj/install.sh rather than make. I was about to give up when I noticed that smlnj/ directory in the distribution archive.)

2005-10-27T22:12:00.000-05:00

Okay, time for the rest of the Startup School writeup.

Michael Mandel — Chief Economist, BusinessWeek

Mandel had a pretty amazing talk. He only spoke from prepared remarks for a few minutes, and then opened up his talk for questions. This wouldn't work for most people, but Mandel was so provocative with his prepared remarks and so broad in his ability to answer questions that it worked.

His talk was about the larger economic context of startup businesses. He said what he's learned about economies can be summed up in four words: "Boom, bust, boom, bust." Furthermore, no matter what stage you're in, everyone thinks it'll never end. Now that there's a bust people think it'll go on forever, but during the Internet boom people thought that would go on forever too. He said that once he was giving a talk called "The Coming Internet Depression" and after the talk, "a bunch of Cisco executives pushed me against a wall and suggestied I should recant, or bad things would happen to my Internet connection."

Economists don't talk about startups very much, but in Mandel's view the chief advantage of the United States is that we foster innovation. Not technology, per se, since that can transfer across borders very easily, but a culture that actually fosters innovation. That puts us in a great position to be the engines of economic growth, since innovation accounts for something like half of all economic growth.

More specifically, he listed some of the US's key advantages:

Financial. The US is, in Mandel's view, the only country in the world with a viable venture capital system.

Human capital. People here are willing to work harder to make innovation happen. The role of a venture capitalist is not to give you money, it's to spur you on to do better. As he said, their job is to throw you out if you have a good idea that you're not executing well, and it's your job to not give them that chance.

The problem with economies driven by innovation is that they're more susceptible to boom/bust cycles. That's why he's worried about China's move towards capitalism: not because they're booming right now and are going to take over the world, but because eventually they're going to have a big old capitalist-style bust and they've got a communist government that may not be able to handle it.

Steve Wozniak

Woz gave a fast-and-furious talk about the origins of Apple Computer in just something he was doing in his spare time. He went much too quickly for me to keep notes, so you'll just have to download it from the Startup School's presentation page to listen to it. One thing that struck me was that we take computers so much for granted that we forget that just a few decades ago they didn't take for granted that a computer game could be written entirely in software, for instance.

Mark Macenka — Partner, Goodwin Procter

Macenka gave a talk called "The Great Value of Avoided Mistakes" about the legal stuff you ought to know about beforehand rather than finding out later on you should've known about. First of all, he said you've got to understand that you need to get cashflow-positive as soon as you possibly can.

Second, you need to know your intellectual property status and be sure where you stand there. Before you get started, know the rights of your former employers, your NDA status, your non-compete status, and so on. Remember that your former employer doesn't have to win a court case with their non-compete agreement, they've just got to scare away the company that would otherwise be buying you; in other words your former employer's rights might be more important than you thought. Also consultants, research sponsors, and the other owners of your company are important considerations at the outset.

A related issue is third-party infringement — if you're using GPL software in your application, for example, be sure you're not using it in an illegal way, and if you are using it in an illegal way make sure you fix it immediately. If you don't fix it immediately it'll just get harder and harder later on, and deals really do fall through based on issues like this.

Also be sure you're clear on who owns what within your group of founders, and make certain you can't get screwed by them. If your not careful, one of your co-founders might quit a few months in and still end up owning half the company, and if that happens you're working for them.

Stan Reiss &mdsah; General Partner, Matrix

"What's venture capital about?" Reiss answered this question from the perspective of a real live venture capitalist. First off, venture capital isn't for everyone, and if you can't make more money by accepting venture capital and its associated strings than you can without it, then you shouldn't take it. (Sounds obvious, but apparently a lot of people don't think about this calculation very much.) That said, VC-backed firms really do tend to have much bigger outcomes than non-VC-backed companies. (Exactly why isn't totally clear, but it could be due to the fact that VC firms are more interested in companies that bigger outcomes, or simply that the good VC firms are really able to make good companies great.)

He also said that while it's tempting to think that venture capital is very hit-and-miss, but the reality is that the top ten venture capital firms are making about 80% of the money of the entire industry, and the list of companies in the top ten have barely changed over the last 30 years. So it's very important to be backed by a good firm, not just any firm.

The question and answer period was pretty weird, dominated mostly by people who wanted to know how they ought to protect themselves from the evil VC companies that were going to listen to their pitch and then steal their brilliant idea to give it to someone else. I was reminded of Paul Graham's comment:

Actually, startup ideas are not million dollar ideas, and here's an experiment you can try to prove it: just try to sell one. Nothing evolves faster than markets. The fact that there's no market for startup ideas suggests there's no demand. Which means, in the narrow sense of the word, that startup ideas are worthless.

Reiss, along with everyone else who talked about VC, pointed out that they're really much more interested in the quality of the people than the ideas.

Stephen Wolfram — Founder, Wolfram Research

Stephen Wolfram told us all about his revolutionary and new ideas about science that in the long run will overturn everything we thought we knew about anything (it's true, just ask him) and in the short run produce nifty ringtones. You can't argue that he hasn't been able to create a successful business, though, and he thought he knew why: first of all, his entire company insists on understanding everything from first principles before doing anything, and that includes everything from the mathematical principles to the design of the user interface. (I haven't used Mathematica enough to know whether this approach works, but it sounds good anyway.) Second, he said that at the core of everything successful is some very hard problem, though it might not be where you expect it, meaning that if you want to start a successful business you've got to be willing to take on hard stuff.

Chris Sakka — Principal, New Business Development, Google

This talk was basically an ad for Google, but it was a heck of an advertisement. He (and his incredibly slick slides that were certainly put together by some graphic designer somewhere) basically said:

Start!
Focus on solving a user problem first and let monetization flow from that solution
Go big!
Make a demo as soon as you can — just talking about stuff won't get you very far; you need to really show people what your product does before they'll be interested.

Sakka also spent a long time talking about how great Google is to work for — on-site laundry, a giant gourmet cafeteria where the whole company eats at once (they like to do it that way so people can sit around and spin ideas off each other), a culture of complete openness, and so on. The clear message was: build a company to be bought out by Google, because if you do and you're good enough you'll get to come work for us.

Olin Shivers — Associate Professor, Georgia Tech; Founder, Smartleaf

Olin basically just went down the list of things he thought people might not know that he'd learned through starting a company. His major points:

Choose your co-founders wisely. You're getting married to them for all practical purposes, so treat it that way.
You should be open about money. People tend to try to be private about that stuff, but it hurts the internal politics of a company more than it helps it.
Venture capitalists: you'd think they're all technically deep, experienced managers who are contrarian and have nerves of steel, and once they're on your side their interests are in making your company successful. That's completely wrong! Most of them are sheep who are just following trends, and their interests may not even be self-aligned, much less aligned with you. He underscored Stan Reiss's point that you really have to choose your venture firm carefully, and hope a good one will take you on.
Failure is a part of the process, but you have to learn from it. Steve Jobs was a big loser, and his endeavors are at best hit-and-miss — but the hits (iPod, OS X) have learned from the misses (Newton, NeXTSTEP).
Related: to start a business, you've got to have a high tolerance for feeling like a moron all the time.
To succeed, you need to be both stubborn and flexible at once. Stubborn in that you need to pursue your goals even in the face of seemingly impossible adversity, and flexible in that the way you get to that goal may need to change on the fly.
You need to work like crazy and be obsessed.

Participants of the 2005 Summer Founders Program

The last talk of the day was by a large group of the participants in Paul Graham's Summer Founders Program. They mostly just took questions, but here's what I took away from their answers:

We had fun!
If you start a company, your relationships will suffer.
Large businesses often don't want to give small businesses the time of day. To have any chance you must be fantastic at communicating.
Make a demo.
Tell people your idea. The kiko.com people in particular said that they were initially very secretive, but they found that most people won't run out and make a competing product the day after you tell them what you're working on, and they're much more likely to give you helpful pointers.
Make a demo.
Starting a company is like jumping off a cliff and trying to build an airplane on the way down.

So that was startup school. Overall, very informative and lots of fun. I can't say I'll do it again next year — I've already learned what I was hoping to — but I'd recommend it to anyone who's at all interested in making a company.

2005-10-26T23:15:00.000-05:00

As I've mentioned before a few times, I attended Paul Graham's Startup School a couple weeks weeks ago. I took lots of notes with the hope of sharing them with you, and then, um, left them in Boston. Mike mailed them to me, though, so I've got them now and I can share them with you. I don't have time to write all of them up at the moment, so this is just part one.

By the way, MP3's of most of the presentations, and those presentations' slides, are available at the Startup School wiki. They're useful.

A general thought: there was a lot of advice given at this event, and a lot of it, I'm realizing now, seems just as relevant to computer science research as it does to starting your own company. Of course the stuff about the venture capital system and finding a way to sell your company for millions might need a little tweaking to apply to research, but I'm surprised by how much of it applies straight across to what I do on a day-to-day basis.

Mike and I biked the mile or so from his apartment to Harvard's Science Center. It was raining like crazy and generally really unpleasant to be outside, but gosh darn it, if you can't handle biking in bad weather you can't handle a startup!

Also the bike I was riding had its seat rusted in place a little too high for me, so biking was that much more of an adventure.

Anyway.

Langley Stein — Co-Founder, TripAdvisor

Stein gave us his six lessons from starting a startup. In his case the particular startup was TripAdvisor.com, a travel-oriented search site, but these lessons apply generally:

Follow your passion
Do it for the right reasons (not money)
Choose your partners carefully
Less is more — raise as little money as you can
Don't be afraid of change
Keep an eye on the exit sign

I didn't realize it at the time, but this was a pretty decent outline for the rest of the day. All of these lessons got repeated throughout the day, so Stein was really giving us the big picture of how all the things we'd learn came together. This talk was where I first got the inklings of two themes: what venture capital is really all about, and how startup companies really make money.

Marc Hedlund — "Entrepreneur in Residence," O'Reilly Media

An "entrepreneur-in-residence" turns out to be someone who sits around thinking about startup companies while drawing a regular paycheck. Anyway: Marc's talk, "Startup Stories," was basically a litany of little parables drawn from the many experiences he's had with startup companies. There are too many of them for me to list them all, but here were a few:

Bloglines.com — turns out this whole site was the work of one guy, who recently was paid a huge amount of money for it (some number of millions, I forget exactly how many). Turns out that a single talented programmer who has a good idea can still make big bucks.
flickr — you've probably heard of flickr as a photo-sharing service, but they actually started life trying to make computer games for girls. They quickly abandoned that idea and went on to make a chat room. The chat room didn't do so well either, but it had a photo-sharing feature that people liked, so the company just made that into their whole product. Even then, they changed around their profit model a few times before they settled on what they've got now. The moral: be flexible! Your first idea may need some refinement (or outright replacement) before it's good enough.
koders — Koders is a search engine for source code. Hedlund pointed out that they had a problem with their business model originally: they'd try to sell ads on their regular site, and then sell customized installations of their search engine to corporate clients. In principle either of these models is fine, but if you're a company you really need to focus on one or the other, since you've only got so many salespeople and so many programmers to make the ideal product for whatever userbase you target. Giving your people two unrelated sales tasks is a recipe for not getting either task done well.

Hedlund concluded with what I think is excellent advice: DON'T START A WEB 2.0 COMPANY! Or more generally, don't chase after the current hot buzzwords. Make your own new hot buzzwords instead, that's a better way to make sure you're on the cutting edge.

Qi Lu — VP of Engineering, Yahoo!

This was the first of two talks by people who might buy you if you're successful enough. It was really mostly about the various Yahoo! subsidiaries that the company bought when they were startups. The technology demos were cool, but since I'm not really interested in making a company that's primarily a web page company and then selling it to Yahoo!, this wasn't super-interesting to me. It is amazing what you can do with some well-placed Javascript and CSS, though.

Hutch Fishman — CFO of cMarket and Veveo

Hutch's talk was all about startup financing and I thought it was fantastic. I knew nothing about venture capital or anything like that, but this talk spelled it out for me pretty well. First of all, one thing you've got to accept is that it turns out that there are lots of companies out there that you could reasonably convince to give you a few million bucks in exchange for partial ownership of your company. Once you've accepted that, the next thing to know is that there's actually quite a bit of structure to these companies, and they give out money in "rounds" that correspond to the various stages your company might be in. Here they are:

"seed" funding — this is a very small amount of money, and your goal with this money is to get you set up with a strategy, an intial business plan, and maybe a demo.
First round — this round is for developing your intial product, and to buy you time and experience with which to develop your business plan, and to put together a team that's larger than just your initial group of founders.
Second round — this is for taking your product to market and filling out your team.
Third round — this money is for expanding: building a sales and marketing team, and taking out any significant risk that's left in your business.
Fourth/"mezzanine" round — this is for preparing for a "liquidity event" (i.e., getting bought) wherein you, your partners, and mostly all the people who gave you money in these five rounds, make a whole bunch of money.

Venture capital firms think in terms of these rounds, and if you can't accomplish the goal of the round with the money you're given, it'll become much harder to get funding for the next round, and so on. Also, funding at the early rounds tends to be much easier to get, but costs a whole lot more in terms of control and amount you've got to pay back. Your goal, as startup founders, should be to own somewhere between 5 and 10 percent of the company by the time it becomes liquid. That seemed shockingly low to me at first, but remember that five percent of $100 million is a whole lot more than 100% of nothing, so taking a bunch of VC money may well be very much in your interest even though when all's said and done they own more of your work than you do.

He pointed out that these days you really are going for getting bought rather than making an IPO, due mostly to the fact that corporate accounting laws are starting to make running your own company prohibitively risky and expensive. It's cyclical, he said, so at some point the pendulum will swing back and nobody in their right mind will want to sell their company anymore, but at the moment your sole job is to make a company that Google or Microsoft or somebody will want to buy from you.

He also stressed the importance of having enough money in the bank to operate for 12 to 18 months, if not for yourself then to present a solid financial picture to your potential investors and buyers. He also stressed that you should get professional accountants, and you should shell out the big bucks for the very best national firms — since you're trying to get bought, you really want your books to be in order. Deals can and do collapse all the time because the books weren't straight.

Paul Graham

Paul read us this speech about how people get ideas for startups. Paul is a great speaker, though I've got to say some of his fans can get annoying in their zealotry. My favorite part of this talk, and probably the part I'll be repeating over and over again as the situation arises, was his story of the new oven at his mother's house:

The average programmer seems to produce UI designs that are almost willfully bad. I was trying to use the stove at my mother's house a couple weeks ago. It was a new one, and instead of physical knobs it had buttons and an LED display. I tried pressing some buttons I thought would cause it to get hot, and you know what it said? "Err." Not even "Error." "Err." You can't just say "Err" to the user of a stove. You should design the UI so that errors are impossible. And the boneheads who designed this stove even had an example of such a UI to work from: the old one!

I think I've already recounted this story once or twice.

David Cavenaugh — Partner, Wilmer Cutler Pickering Hale and Dorr

This was about intellectual property. I actually happen to gave gotten a really well-done hour-long lecture once in undergrad all about intellectual property, so I knew all of this stuff, but if it's new to you you might want to check it out.

Okay, after that was lunch. The White Sox have just won the World Series as I type this, so I should probably take off and join the revelry for a bit. I'll give you the exciting conclusion of what happened after lunch later on.

2005-10-23T23:55:00.000-05:00

Now a brief word in praise of my programming language implementation of choice. I decided three or four days ago that if I'm serious about the whole studying-language-interoperability thing, which it appears I am, I really ought to know something about actual language interoperability systems. So I picked for myself a modest little project: implement a standard CLR-style binary heap in C, where heap elements were abstract pointers and when you create a heap you've also got to pass in a less-than function with respect to which the heap will remain balanced. The heap algorithms are all dead simple, so I figured that even though there's a little rust on my C programming skills it wouldn't be too bad.

I did the code yesterday and was able to write make-heap, insert and extract-min functions pretty quickly. There was one maddening oddity, though: in my test harness, if I printed out each number as I inserted it, everything went along fine and I could insert as many numbers as I wanted to and then suck them all out, no problem. If I didn't print the numbers as I inserted them, things went all crazy and I'd end up with nonsense in my heap. Now, I haven't forgotten enough C to not realize that this was a classic memory problem, but the particular manifestation was driving me crazy: I couldn't watch what was happening at all because whenever I put a printf statement anywhere interesting the problem disappeared. I stepped through the algorithm in my head over and over again, and couldn't find anything wrong in any of the three algorithms I'd implemented even after extensive staring. So I gave up.

But it ate at me, and so today I came back to the problem. I didn't even care about interoperability anymore, I just wanted to figure out where this bug could be coming from. Long story short, after about three hours I discovered it: suffice it to say, despite their amazing visual similarity sizeof(void) and sizeof(void *) are not the same thing, and if you malloc the first and mean to malloc the second you may end up getting surprised.

That fixed, the library snapped into shape and after a rather-longer-than-it-should've-been digression on how to build dynamic libraries in OS X (gcc -dynamic -g -c yourfile.c && libtool -dynamic -o libyourfile.dylib yourfile.o, in case you're curious), I was ready to try bringing the library into DrScheme and calling it from Scheme code. Ten minutes later:

> (define h (heap 20 <))
> (insert h 10)
> (insert h 9)
> (insert h 8)
> (insert h 7)
> (extract-min h)
7
> (extract-min h)
8
> (extract-min h)
9
> (extract-min h)
10
>

This even though I'd only ever used the PLT foreign interface once before, and never with higher-order functions or C functions that made callbacks or any of that stuff. I was very impressed.

2005-10-20T17:56:00.000-05:00

On Sunday, I had a meeting with Mike and Dave to discuss the future of Topsl. One very productive decision we all finally came to agree on at this meeting is that a web survey is inherently a two-phase computation: one phase that runs statically (i.e., before anyone takes the survey) with and one that runs dynamic (i.e. as someone is taking the survey). The static phase just takes the survey from something the user types in, which might have convenient abstractions or computations that are only meant to happen once or whatever, to a fully-elaborated program; that program then runs as the dynamic phase.

So as we were talking about that, Dave or Mike (I forget who) brought up a problem. If you want to perform a map over a list of, say, strings to turn them all into questions, that's no problem. On the other hand, if after you've done that the survey author contacts you and says they want to add the currently-logged-in user's name to one or all of those questions, now you're screwed: you don't have static access to variables bound at runtime, for the obvious reason that their values aren't known yet. That causes a big problem wherein a small tweak can force a large reorganization, something we all wanted to avoid. So we had the idea to have an opaque value representing a variable bound only dynamically by Topsl but available statically, so as long as you don't actually need to observe the value of the variable you can include it when you're generating Topsl code.

Today, in a totally different context — discussing my NEU talk of Monday — Eli pointed me towards the notion of "exotic functions" in higher-order abstract syntax and how one approach to eliminating them is to just give variables an opaque type as far as the metalanguage is concerned, which guarantees that you won't use their values for anything. The type system simply won't allow it. If you think about it, that's a typed version of the exact same solution we discovered, and that connection opens up the whole world of HOAS and fresh languages to Topsl.

So, so far, Topsl is related to fresh languages, multilanguage semantics, domain-specific languages, various approaches to static analysis, and staged computation, at least. Is there anything this goofy programming language isn't related to?

2005-10-18T14:23:00.000-05:00

Lessons learned from my Northeastern talk:

If your talk is about something abstract, make it concrete with an extended analogy that you thread through. I opened with some talk about Mars and Earth and how they want to interact but the Martians are afraid of Earth germs, and threaded that through the entire discussion. I thought it might seem to cutesy and the audience of staid and serious computer scientists wouldn't go for it, but I found that even staidest and seriousest people there were completely happy to think in terms of forcefield-encapsulated Martians travelling to Earth and so on. If anything I think it actually really helped the audience understand what was going on, based on the evidence that audience questions seemed to be phrased in "Earthlings versus Martians" terms much more often than "Scheme versus ML" terms even when my slides weren't talking about that analogy at all.

If you follow point 1, make sure you understand that extended analogy perfectly! Like I said, I added in all my discussion of Earthlings and Martians last week; I've been working on this line of thinking for a year or so at least and so the Earth/Mars/forcefield way of looking at the problem is something I translate my thoughts into rather than a tool I use to think about the problem in the first place. For my audience, though, it was the other way around, and as a result I think they actually saw the analogy more clearly than I did myself. I got a question about whether you had to wrap Martians-in-forcefields in Earth forcefields to send them back to Mars (this being an analogy for sending a foreign value back to the language it comes from). I heard "When you're sending a value back to its host language, don't you need to make it completely opaque to that host language?" and answered "no"; but the analogy doesn't actually quite work that way and the answer really ought to have been "Yes, and forcefields cancel each other out." People really really didn't like that answer, and for a while I thought the audience was going to revolt and refuse to buy a central premise of my talk. Turns out they actually understood what I was saying better than I did and were correcting me.

Practice practice practice, and find someone to listen to you do it. The more you practice the wording and delivery of your talk before you give it, the better it will be, and having someone listen to your talk can be invaluable to telling you where you're being confusing, where you're belaboring things, and where you're doing well (also how funny your jokes are). Don't decide exact phrasing you're going to use on the spot. Of course this advice is obvious and something I already knew, but every time I give a talk it amazes me how much just going through it a few times with a couple people makes it go from awful to good.

Don't suddenly discover a few hours before your talk that you've got a non-negotiable deadline an hour after your talk finishes. I can't stress this one enough.

It's much more fun to give a talk to a bunch of smart researchers whose interests are closely aligned with your own than it is to give a talk to a more general audience.

By the way, people have requested my slides, so I've put up a little companion page that has both the slides themselves and the reduction systems I talked about encoded as PLT Redex programs.

2005-10-17T22:12:00.000-05:00

So I just got back from an incredibly hectic, amazingly productive three-day trip to Boston, at which I attended Paul Graham's Startup School, had a long meeting about the future of topsl, and gave a talk at Northeastern about the semantics of multilanguage programs. I will have more to say about all these things later, but for now I'd just like to give a big thanks to the folks at Northeastern and the Boston area for coming to my talk and being such a great audience. I've never given a talk before where everyone was so obviously attentive and understanding of what I was presenting, nor have I ever felt so nervous that halfway through the talk someone would raise their hand and destroy my entire talk. Great fun!

2005-10-10T18:17:00.000-05:00

Hi all. Sorry about the lack of updates of late — I've pretty much been racing to get things done in time for my Boston trip and haven't had time to write a proper update. Good news is that I heard back from the Startup School folks and they have accepted my application, so I'll actually get to attend the school around which I planned my trip and I won't be flying out there just to spend a weekend in scenic Boston.

Actually, my weekend has quickly filled up, and I'm busy pretty much continuously the entire time I'm there from touchdown to takeoff, with my Northeastern talk, Startup School related stuff, visiting my sister, and my being an invited speaker at the esteemed Topsl Periodic Summit run by the biggest names in the hot area of PLT Scheme web-server-based psychology questionnaire language research (i.e. Mike and Dave). Who knew there was so much for me to do in Boston?

2005-10-02T20:37:00.000-05:00

Okay, here's the ICFP conference report, part one, including our trip out and the Scheme Workshop.

Maurice, Robby and I set off last Thursday from O'Hare to Schiphol Airport in Amsterdam, and from there to Tallinn Airport in Tallinn, Estonia. Strangely enough, as we were leaving O'Hare we ran into Matthew Flatt and a small entourage; strange because they started out in Salt Lake City and were going to Tallinn via a totally different route, but they happened to pass through O'Hare right as we were leaving. As you'd expect, there were about a million people going to Amsterdam for a million different reasons, but the people going from Amsterdam to Tallinn were much more likely to be headed for ICFP. At Schipol we ran into Paul Hudak, Mitch Wand, Dan Friedman, Eli Barzilay, Danny Dubé, and Ronald Garcia, all of whom were headed to the conference.

We arrived, and after we checked in to our hotel Maurice, Scott and I wandered around the city a bit to find the conference venue and get our bearings of the city. Here's a picture from then:

The next day was Scheme Workshop day. Here are my notes about that:

Type Classes Without Types
Haskell's type classes are good for facilitating C++-template-style "generic programming" — how can we get the same in Scheme? Ron Garcia introduced the idea of "predicate classes" that are like typeclasses but dispatched dynamically based on a predicate. Unfortunately there's a modularity problem with these — it's impossible for two modules to introduce two predicate classes each, where in each module one predicate class is more specific and one is more general than a typeclass in the other module. But it seems like a nifty programming paradigm related to predicate dispatch, and I'd sort of like to try it out.

Eager comprehensions
Sebastian Egner explained the design of SRFI 42, eager comprehensions; eager comprehensions are a sort of analog to Haskell comprehenesions that construct the list immediately rather than lazily. This was a very comprehensive talk, and Sebastian really gave the impression that he'd thought his design through. He even gave several performance numbers for the reference implementation. This was the first of two talks about Scheme loops we'd see over the week.

Abstraction and Performance from Explicit Monadic Reflection
So you want to thread a value through a scheme program and thus you use a monad. But you don't want to use the normal monadic combinator implementation because they're too slow. On the other hand, you really don't want to write the code without monads because you also really care about code clarity. So you use macros to implement the monads, and a thing called "monadic reflection". Jeremy Sobel's talk was energetic and fun.

An Operational Semantics for R5RS Scheme
This was my talk. Exciting! I'm not sure whether people followed me, or fell asleep, or what, but I think that at least some people followed me and appreciated some of the details I was trying to bring across. Most excitingly I found out that Martin Gasbichler has used PLT Redex to encode a hygienic macro system.

After that was lunch, followed by:

Commander S — the Shell as a Browser
A program written on top of scsh that improves with two major new features: a plug-in architecture for implementing "views" of particular commands' outputs, and a novel approach to job control. Pretty neat-looking. In Q & A people asked about piping — you'd like to be able to incrementally construct pipes, which seems like something Commander S should be able to facilitate, and also it's not obvious what view to use on the output of a pipe. It turns out this is an area where the system hasn't been fully fleshed out yet.

Ubiquitous Mail
Manuel Serrano showed us all about synchronizing IMAP servers with a Scheme system called bimap. The most interesting part was when he showed that you can use bimap to write Scheme programs for general mail processing, to implement policies like whitelists or whatever.

Implementing a Bibliography Processor in Scheme
I had never really thought about BiBTeX before, but it turns out that like all things TeX-related it's creaky and barely works and needs to be replaced. The author presented MLBiBTeX, a replacement with special multilingual features originally written in C and rewritten in Scheme.

The Marriage of MrMathematica and MzScheme
Chongkai Zhu presented his interface between PLT Scheme and Mathematica. It's neat to see these languages connected together.

ACT Parameterization Framework
An simulator for internal combustion engines written in Scheme.

Javascript to Scheme compilation
The author presented a neat Javascript compiler that compiles to Bigloo scheme. The semantics of Scheme and Javascript are similar, so mapping Javascript onto Scheme class systems seems to work well, and once the code is in Scheme they're able to take advantage of the excellent Bigloo compiler to get fast code. Performance is better overall than any existing Javascript system, though that's not fair since their compiler isn't quite ECMAScript compliant. During Q & A, they explained that two features it doesn't support that will likely hurt its performance are string-based field/method access and modification of globals via the global object. Overall this seemed like a very cool piece of work.

Okay, there's more to write up but I figured I should at least get the Scheme Workshop report up. More to follow.

2005-09-26T03:56:00.000-05:00

Hi. Sorry on the lack of updates — I've got net connection, but it turns out I've been way too busy to write proper accounts of the talks so far. I have been keeping notes, though, so I'll catch you all up as soon as I can.

Estonia itself is quite a strange place, Old Town is a very-old-looking area and it's difficult to tell what's real and what's a recreation. Parts of it are very pretty, though, so that's nice.

More later ...

2005-09-24T00:50:00.000-05:00

Greetings from Tallinn! Looks like I've got Internet access at the conference here. More later ...

2005-09-22T08:06:00.000-05:00

So it seems that other people have noticed the article I linked to in my last post too. Matt Jadud over at Untyped wrote an interesting rant about about it that points out its obvious deficiencies. In the course of doing so, he points out the ACM's Model Curricula documents, a great resource I didn't know existed before. I can't yet comment on the particular documents, but Matt's comments about them combined with the obviously tremendous effort they must have been to create really illustrates that teaching is very very hard.

Dave Herman noticed my post and comments on my definition of computer science. I suggested that it was "the study of how to best systematically solve problems"; Dave prefers a more general formulation by Raatikainen: "How do we automate?" I made a comment over on his weblog about it which you can read over there if you care to. (Just realize that when I wrote it there were three comment spams above it that said things like "Great post! There are lots of resources on my web page about immigrating to Canada!")

Anyway, I'm headed off to Estonia later today for the Scheme Workshop and ICFP. I hope I'll be able to update this webpage from there; if so I'll try to do a regular conference update as it goes on, and if not I'll try to take good notes and do one comprehensive update when I get back.

2005-09-18T01:16:00.000-05:00

For as long as I've been paying attention to computer science as an academic field, people have been arguing about how to design an undergraduate curriculum. To what extent is CS a branch of math, or of electrical engineering? How should academic CS be tied to industry? To what extent do we teach good-programming skills like modular design or "design patterns" or abstraction (which has apparently been discovered yet again and dubbed the "Don't Repeat Yourself" principle by the Ruby people), and to what extent do we teach more academic subjects like computability, rigorous asymptotic analysis and the like?

I found today that O'Reilly's OnLamp website recently ran an opinion piece on the subject. If you take even a glance at it you'll see that the author is very much an industry-only guy and it's tempting to just say that if he thinks diplomas from DeVry are more useful than ones from MIT then it's just his loss. But though I think this article betrays its author's fundamental misunderstanding of what a computer science education is all about, and as much as I think some of the `academic' skills he denigrates are actually quite a bit more useful than the `practical' skills he praises (hey, I'm a PL person, I think every problem is a compiler problem!), I'm going to go out on a limb and say he's got a good point. More specifically, I think his list of things that CS departments ought to be teaching probably contains more good ideas than bad ones.

The way I read it, his list breaks down into two major categories and a little miscellany. The first major category is what I'd call programming competence, which he addresses with the items:

The basics of Programming
Problem analysis
Basics of good code architecture: Loose Coupling, etc.
Testing, Debugging, Performance, Re-factoring
Code Reading
The importance and tools of Planning
Patterns and Anti-Patterns
OO Design, Interfaces
Architectures: client/server, SOA, P2P, etc.

What these things have in common is they're all skills that have nothing to do with particular problems but only with managing the general difficulty of writing a program, particularly a big program that needs to exist for a long time. That isn't usually thought of as a core CS topic, but it should be: computer science is fundamentally the study of how to best systematically solve problems. The academics have traditionally decided that 'best' means 'using the smallest set of resources possible,' but in situations where resources are relatively abundant and programs live a long time I think it makes more sense to define 'best' as 'most maintainably'. Therefore I see no reason why topics like abstraction shouldn't be considered as fundamental to computer science education as efficiency is.

The second major category is what I'd call modern programming cultural awareness. I'd include these items:

Real world Databases
A 'Big' language or two (Java, C#, C/C++)
A scripting/'agile' language or two (PHP, Perl, Python, Ruby)
XML (DOM/SAX, XSLT/XPath, etc.)
Internationalisation, Localisation, Encoding, Unicode
Interface Design, Usability, Accessibility, HCI
Security
Common Protocols (TCP/IP, HTTP, SMTP, FTP)
Source control, change management
The typical Software lifecycle
Metadata, Information Architecture, etc.

These are all about learning the state of the art in industry for solving various problems. I certainly don't think a CS undergrad should focus on this — that's what industry is about, after all — but I can't say I'd be that happy graduating a CS undergrad who didn't know anything about any of them. To the extent that computer science is an engineering discipline, its practitioners ought to have a working knowledge of the great feats of engineering that have already been done, and ought to be conversant in the language the engineers use. As a programming languages researcher, I'm not a big fan of C++, say, but it's so much a part of the culture that it was absolutely useful for me to have learned it.

And then there are some miscellaneous items. I certainly agree that anyone with a bachelor's degree ought to learn about Grammar, punctuation, concise and clear writing but in general these points are kinda silly. And of course this list leaves off practically the entirety of what computer science is traditionally about, and I don't want to give anyone the impression that I think we ought to replace all our algorithms and computability classes with lectures about design patterns and Unicode or that SAX vs DOM ought to replaces P vs NP. And please don't take me to mean that I basically endorse this guy's view of how CS departments ought to be. But I do think that academic CS and the programming industry benefit very little from each other's existence, and that's a shame. Physics, biology, and even psychology enjoy a fruitful exchange of ideas between their industrial and academic branches — computer science should too, and I think those of us in academia can do our part by trying to understand the industry programmers even when they don't seem to understand us.

2005-09-15T01:30:00.000-05:00

This is an odd, reasonably pointless expression that returns 7 in any R5RS-compliant Scheme implementation:

(let ((x (lambda (z) z)) (y 7))
    (let ((x (lambda () x))) y))

This is an infinite loop in any R5RS-compliant Scheme implementation:

(let let ((x (lambda (z) z)) (y 7))
    (let ((x (lambda () x))) y))

Gotta love overloaded syntax.

2005-09-14T17:50:00.000-05:00

So, I'm a big fan of the "everything I do appears on Lambda the Ultimate" policy.

I'm pretty surprised about this latest mention, though, since I'd figure that only a pretty narrow range of specialists would make it past the abstract.

2005-09-13T16:02:00.000-05:00

Finally! As of today, I am done with my Scheme Workshop paper.

Now all I've got to do is figure out how to keep an audience awake for 45 contiguous minutes while at the same time presenting the material that paper contains ...

2005-09-10T13:19:00.000-05:00

Strange how things work out. I scheduled a more-or-less spontaneous visit out to Boston, nominally to do a few things related to online surveys but more realistically just to see the people I know out there. I mentioned to Robby that I was going, he called Matthias, and now I'm going to be giving a talk at Northeastern about the interoperability stuff.

The Meaning of Multilanguage Programs

Jacob Matthews
University of Chicago, Chicago

Monday, October 17, 2005

Software developers have long understood that real applications are built out of components in different languages and connected using a variety of different strategies. For example, foreign function interface systems like SWIG connect high-level languages to low-level languages; component frameworks like COM and CORBA connect high-level languages to each other; and domain-specific languages such as Yacc are embedded into their host languages in such a away that control and data flow back and forth between the programs.

In this talk I will present a general technique for modelling the operational semantics of multilanguage systems such as these. The technique is simple and general, and surprisingly connects traditional multilanguage systems to seemingly unrelated concepts such as contracts.

Joint work with Robert B. Findler

Pretty cool. I'm very excited about this talk because it'll be the first time I'll have given a public talk about the interoperability stuff, though it's probably been nearly a year that I've been working on it. Also, since the talk will be on October 17 and ESOP's deadline is October 14, I may decide to take my talk outline and turn it into an ESOP paper as I'm writing it. That'd be good. I've already figured out easily enough for a paper, but I haven't really properly documented it yet, so this will be a good opportunity for that.

2005-09-06T20:47:00.000-05:00

The Scheme Workshop paper revisions are done — it's been massively rewritten since the first submission, so hopefully people will find it clear and useful. Even for computer science, in which paper turnaround time is a few months rather than a few years, writing and revising papers seems like a distraction from research sometimes. Of course writing things up is crucial, but I'd much rather be making progress than fiddling with figures and wording to make the things I was working on last year make sense to other people.

Unrelatedly: there's been a lot of activity with the PLT web server recently, and a lot of new features are coming in. There's now a new feature that allows a servlet to attach a special k-url handler to expired k-urls — finally it's possible to give good servlet timeout messages! I can't tell you how much it irked me that there was no good way to give someone a message telling them that their session had expired and what to do to make things work again.

2005-08-26T00:24:00.000-05:00

I learned today that PLT Scheme actually has two kinds of thread-local storage boxes: parameters, which everybody knows about, and thread-cells, which as far as I can tell are not well-known at all even among PLT developers. The difference is very subtle: parameters are attached to a continuation and thread, thread-cells are only attached to a thread. That makes no sense, I know, but maybe it will with a code example:


(define p (make-parameter #f))
(define t (make-thread-cell #f))
(define k #f)
 
(begin
   (thread
    (lambda ()
      (parameterize ((p 'thread-one))
        (thread-cell-set! t 'thread-one)
        (display "In thread 1:")
        (newline)
        (let/cc my-k (set! k my-k))
        (printf "param: ~a, tc: ~a\n" (p) (thread-cell-ref t)))))
  
   (sleep 1) 
  
   (thread
    (lambda ()
      (parameterize ((p 'thread-two))
        (thread-cell-set! t 'thread-two)
        (display "In thread 2, throwing to a continuation created by 
 thread 1:")
        (newline)
        (k 'dontcare)))))

This prints out:

 
In thread 1:
param: thread-one, tc: thread-one
In thread 2, throwing to a continuation created by thread 1:
param: thread-one, tc: thread-two

The second half of the printout is the interesting part. It shows that a continuation stores the parameter settings in effect when it is captured and carries them to new threads; it does not, on the other hand, capture the current values of thread-cells. This makes thread-cells, despite their obscurity, the better choice for implementing a lot of things; for instance, in an OS-like program that uses continuations to represent user processes and threads to represent particular slices of computation, thread-cells are the right abstraction for holding onto the OS resources that are particular to a thread.

That example wasn't pulled out of thin air, of course. It's actually how I came to learn about thread-cells at all, in fact; the PLT web server had an odd bug that cropped up because some resources that should be thread-cells were parameters instead, the result of which was that servlets that tried to save continuation objects occasionally found that when they eventually threw to them the servlet would die abruptly.

This is now fixed, and to celebrate I released a somewhat nifty new PLaneT package that highlights the power of being able to write abstractions over web interaction patterns rather than just web pages: resume.plt.

2005-08-19T10:28:00.000-05:00

So, I've been working a lot recently revising the R5RS semantics paper for the 2005 Scheme Workshop. In doing so I've discovered a lot of interesting R5RS quirks; here's one I discovered just recently. To my knowledge this hasn't been pointed out before, and it might well be a widespread example of R5RS nonconformance among Scheme implementations.

The R5RS seems to avoid specifying how continuations interact with the top-level environment deliberately, the only discussion being: "The continuation represents an entire (default) future for the computation. If the expression is evaluated at top level, for example, then the continuation might take the result, print it on the screen, prompt for the next input, evaluate it, and so on forever" (section 6.4). However, R5RS section 5.1 says: "At the top level of a program (begin ...) is equivalent to the sequence of expressions, definitions, and syntax definitions that form the body of the begin." So because when you type in (begin E₁ E₂ ...)that's exactly the same thing as just typing in E₁ followed by E₂ and so on, whatever continuations do with the top level, they should do the same thing whether or not they're in a top-level begin form, right?

I tested every Scheme implementation I could get my hands on, and this wasn't true for any of them when it comes to continuations. Here are the expressions I used:

(define num 0)
(define k (call-with-current-continuation (lambda (x) x)))
(set! num (+ num 1))
(k (lambda (x) x))
num

and


(begin
  (define num 0)
  (define k (call-with-current-continuation (lambda (x) x)))
  (set! num (+ num 1))
  (k (lambda (x) x))
  num)

Try them in your favorite Scheme interpreter's REPL and you'll probably find that running the first yields 1 and the second yields 2. I tried it in mzscheme, guile, MIT Scheme, and Bigloo (the four Scheme interpreters I've currently got installed on my work computer) and that was the result in every case.

The only difference between the two pieces of code is that one's in a top-level begin and the other isn't, so clearly the R5RS specification that the two programs be equivalent isn't being followed. What's going on here?

What's going on here is that call/cc is exposing an implementation detail, as it does with so many features. My advisor suggests that the simplest way to implement a REPL will have a single evaluation context (i.e., what gets grabbed by call/cc) for every top-level expression it evaluates, and that the code that implements top-level begin uses that same continuation for all subexpressions rather than making a new one for each, meaning that the REPL's prompt is actually a prompt in the control-delimiting sense in all cases. Of course in that case you'll get the behavior I observed.

That behavior seems fine to me; in fact, considering that every Scheme implementation I tested does it this way it's probably a better way to do it than the way the R5RS suggests.

2005-08-11T20:56:00.000-05:00

I had a pretty abbreviated day today for various reasons, but I managed to get another new feature into PLaneT -- now it's possible to use the command-line tool to download PLaneT packages without installing them, so people with only intermittent Internet access can use PLaneT more easily. I've resisted features like this in the past on the assumption that people would tend to forget about the fact that PLaneT will do everything automatically for you if you let it, but I've come around lately to the opinion that I shouldn't remove features just because they can be misused.

I also had an epiphany about how to structure web servlets to implement save points in a web application that ought to be associated with a user rather than with a session. The answer is pretty simple in retrospect - use a table that maps users to continuations, capture a new continuation just before sending off any web page and bang the table to point to that continuation (removing any old ones), and throw to that continuation whenever the user logs in - but I actually implemented this feature a much harder way for the speed-dating project without ever realizing I could get the same effect for the cost of about ten lines of code if I just used the power of first-class continuations.

The fact that this was done in the context of a continuation-based web server makes the whole thing a little more ironic, but actually it sort of makes sense: the continuation-based web-server makes you think of continuations as the same thing as URLs, so when you have a problem that involves continuation-manipulation the natural thing to think of is rephrasing it as an HTTP redirect of some sort - perhaps saving URLs as they went by and doing an HTTP redirect to the last one of those a user had seen. I scratched my head over that for a long time and realized it didn't quite work, but didn't quite understand the essence of the problem and its solution. Like I said, I actually went off and implemented the whole thing a different, awful way that was a complete beast to maintain and never really worked exactly right.

But today I found myself saying, in trying to explain the issue to someone else, that the continuation you associate with a URL is taken one step too late: it will return _after_ the web page gets shipped off, not beforehand as it should. From that perspective the answer is obvious - if the continuations the web server provides don't work out, grab your own! Scheme has no problem with that, and the fact that the continuations aren't connected to URLs is completely inconsequential. The same solution would apply to any situation where a user wants to save and resume their session, on the web or off. You've got to love the fact that Scheme gives you power tools like call/cc -- very rarely used, but indespensable when they are.

2005-08-10T22:19:00.000-05:00

I think last night's hacking got me eager to break out of my theory tower and do real programming, and Noel's email about using PLaneT over HTTP gave me the final push I needed to finish off PLaneT's HTTP support. I'd been planning that support for a long time, even to the point where I had a complete implementation strategy, but I never got the motivation to actually program until today. I still think PLaneT's original protocol is a better fit for the problem PLaneT solves than HTTP is; the original goal was and still is that the client and the server have a little conversation about all the packages that the client will need to download, then the client downloads them all at once, just like the linux package manager systems out there. Unfortunately there are enough problems implementing that on both the server and the client that the protocol doesn't do any particular good for actual PLaneT communication; its only real role was stopping people with restrictive firewalls from using the service. That's what the HTTP client fixes, and it's fixed now. Fun fun fun! And, it meant I got to play with the web server some more to do things it doesn't often do, and that meant I discovered a few more issues (mostly docs bugs, one annoying design limitation).

2005-08-10T02:25:00.000-05:00

I think you can feel like a computer scientist at any time of the day, but you can only feel like a hacker after midnight. I was helping Mike with a PLT-server based project (another Topsl project, as it happens) and after a certain point a nasty, nondeterministic bug started cropping up and eating our results. After a long while of looking over our code, we came to the conclusion that there was at least an equal chance that the bug was in the server; I've got some experience with the PLT server so I dove into its guts hunting for the problem. Long story short, I propped open my drooping eyelids and shortly before 2:00AM I was able to confirm the bug and verify a workaround. I'm pretty pleased with myself for finding that.

Other day's computer stuff: not much interesting to report. I rewrote a section of the R5RS paper, then rewrote it again, then wrote a formal system used in that section, then threw it away and used another one that I didn't realize had already been written; then started rewriting that one. Kathy and I also made a couple stabs at one of the core systems for a new paper we're working on together that extends on a bunch of stuff we both done independently; we just started this a few days ago, though, so there's not really much to say yet.

2005-08-09T09:01:00.000-05:00

It's becoming more clear to me that there's something lurking below the surface that relates contracts, foreign function interfaces, macros, and probably subtyping and (more speculatively) component systems in general: the notion of us versus them, negotiating our differences, and statically or dynamically keeping track of who we and they are. Contracts and foreign function interfaces keep track of us and them dynamically for the purpose of blame or conversion, respectively; a macro author builds up a semantic notion of us (the macro construct) versus them (the host language) that he or she then has to write a program to translate away. Subtyping contains a totally static version of the idea where we,an expression, may disagree with them, our context, about what our type is, but we can in some circumstances amicably resolve our differences.

I haven't worked out most of those examples yet, so I don't know if the connection is anything beyond superficial, but it seems pretty compelling to me after having worked out some toy examples. I'll have to investigate further.

2005-08-03T19:59:00.000-05:00

If you're interested in the continuation-based web-site authoring systems like the PLT web server and Avi Bryant's Seaside, you may well know about UnCommon Web. Just recently, UnCommon Web's author Marco Baringer made a Quicktime movie (.torrent) wherein he showed how to build up a simple interactive site using UCW; I checked it out today since I'm always curious at how people are taking the continuations-as-web-programming-paradigm idea. It's about 20 minutes long and really worth watching. It looks like at a very high level the code is organized in roughly the same way you'd organize it using the PLT server (no surprise), but instead of having programs periodically call a send/suspend procedure, instead they periodically send objects(?) called components that appear to represent web pages a "show" message that behaves as send/suspend does. This isn't a big deal but does seem to cause the code for individual pages to look different at a micro level. I am a little hesitant about that, since I've long since decided that organizing a web site's code around the web pages it displays is not the right way to do things most of the time, but I really don't know enough about UCW to say whether it's really a problem.

Other than watching that video, I spent much of today revising the Scheme Workshop paper; I have to say thanks again to the reviewers who really honestly gave me tons of very useful feedback. I've completed a once-over pass that fixes most of their complaints; the only thing left to do now is the unpleasant task of creating a new section and doing some major surgery on another. That's complicated by the fact that the paper is sitting right on the page limit as it is, but I suppose that's always how papers go.

In other news, it seems that the Fortress team is using PLT Redex to model the dynamic semantics of "Basic Core Fortress" (see page 104 of the new language specification). Neat!

2005-08-01T21:53:00.000-05:00

Hm, I see I forgot to mention that I was on vacation for the last week. Well, I was on vacation for the last week; specifically, Molly and I went down to Atlanta to visit my parents, raft down the Chatahoochie River, watch various plays and movies, enjoy the coastal Georgia beaches (I saw a baby sea turtle climb from its nest and march down to the ocean!), and generally do things that do not at all involve programming.

I'm still catching up with my emails, but I was happy to see that our "Operational Semantics for R5RS Scheme" paper was accepted by the Scheme Workshop, and I was even more happy to see that the reviews we got were extraordinarily helpful. All three reviewers really dug into the paper and identified a lot of ways we can make the paper stronger, while at the same time giving me the warm fuzzies with their positivity.

I also turned in my final grades for the class I taught over the past five weeks. My final exam was quite a bit harder than my midterm exam, but it seems like it served its purpose pretty well in differentiating the students rather than crushing them all and making them cry. Nobody got a perfect score on this one, but there were definitely solid A's and B's and so on. After I finished grading it, I made the final calculations and got my students' raw scores, curved them (I actually did pretty well, the curve was a just uniform five points all around, and really if I wanted to be a bit more of a tough guy I could've safely omitted it) and made that my final grade. All in all, I'm feeling pretty good about my class at this point. I will see whether I actually learned anything about teaching in the fall when I have to do it all over again, more slowly and with more students.

2005-07-20T17:28:00.000-05:00

Paul Graham seems to be slipping ... :)

Today I taught my last class of the quarter (Friday is the final), in which I gave a lecture introducing computer science, the whole discipline, starting with NAND gates and how you'd coax electricity to behave like boolean logic, and ending up with the P=NP question and the halting problem. I don't know whether my students cared about it, but for me it was great fun.

2005-07-19T20:16:00.000-05:00

Well that sucks. We just couldn't get our multilanguage semantics paper together for the POPL deadline; we could've submitted a badly-written, unclear paper, but we talked about it and decided this work was strong enough that it should get a proper treatment. And with teaching and the programming contest and various other scheduling conflicts, I just haven't had time to give it what it deserved. That doesn't just mean that I didn't write it up clearly enough, but it also kept us from identifying a couple of good, small but significant extra pieces of research we should've done. Nothing major, just some extra systems we should've built that would strengthen the narrative.

I'm happy with that decision and I think it was the right decision, but it does create a problem: it doesn't look like there will be a suitable venue to publish this work until at least next year's ICFP, which is more than a year away, and this work is more suitable for POPL anyway (for one thing, it has nothing necessarily to do with functional programming but has a lot to do with the principles of programming languages in general). So I think I'll do the extra research we decided on and then write up a tech report. We'd need to do a tech report version of this paper anyway since at one level it's all about proving type-soundness of a whole bunch of multilanguage systems, and putting it out there as a tech report will finally give me something I can point people at when they ask me what I'm doing. Once a conference comes around that seems appropriate, we'll take the report out and submit it. Not ideal, but probably the best available option. And I'm really confident in the work itself; we continue to find more fertile areas to explore within the framework we've made. I think when we put the report out you'll agree that it was worth the wait for us to do it right.

Anyway, from other fronts: my class seems to be going well and we actually managed to go a little faster than they did during the regular year. I think they've been able to absorb things pretty well, though the stuff we did at the end (graph algorithms in various guises) is pretty tough for people with only five weeks' experience. We'll see how much they've retained on Friday when they have their final.

2005-07-15T19:18:00.000-05:00

Been a little while since my last update. I've essentially been working on most everything I do, all in little bits.

The morning I spent dealing with a few different PLaneT issues. First, I fixed a bug in the webpage generation code that I swear I've fixed before; it was actually the confluence of two bugs, one of which was that "metaprogramming" was inadvertently left out of the list of possible categories and the other of which was that packages with no legal categories were inadvertently getting omitted from the web page entirely rather than being filed under "Misc" as they should've been. Both bugs are fixed now and a few packages that weren't getting listed before are showing up. I'm just about sure I fixed this exact bug long ago, so I have no idea why the problem re-emerged. Strange. The second bug was actually a bug in DrScheme; it turns out that you can't distribute a new language level using PLaneT because of an assumption DrScheme made that worked at the time but got invalidated when PLaneT came along. I'm not going to fix that one myself, but the proper people got notified so hopefully it'll be fixed soon.

On my class front: I taught accumulator-style recursion and generative recursion, capped off by teaching the topological sort and breadth-first search algorithms today. I don't know how well my students would do if I asked them to reconstruct those algorithms from memory, but they seemed to be able to follow along well enough during class so that's good.

I'm also writing a paper for POPL, and despite the full-time job of preparing for my class I've been able to make some decent progress on it. I've got a draft and I'm currently going over it again, revising prose and fiddling with formalisms and so on. I think it's pretty interesting stuff, though as with everything it's difficult for me to judge it having worked with it so closely for this long. And as with anything theoretical, I'm constantly in fear that everyone but me will think it's obvious and not worth spending a whole paper talking about. We'll find out what the editors think.

2005-07-08T23:54:00.000-05:00

So if you recall from yesterday, I was really worried about the test I was set to give today. It's amazing, I honestly was worried to death about whether I'd made the test too hard, whether nobody would be able to finish it, and so on. I was convinced by several people that I'd made it too long for an hour, so I bumped up the time to two hours, but I was having horrible visions of nobody being able to finish even in that time and having everybody fail and hate me.

Well, I gave out the test today (here it is, in case you're curious). First of all, four of my six students finished in one hour. Second, I actually think it was too easy for most of them — pretty much everybody got the idea of everything, and most pretty much did everything right. If I'd have known that, I probably would have changed problem 2 to deal with 2-3-4 trees instead of plain trinary trees and I'd've made the function they had to write for it something fancier, maybe making them drop every leaf to the minimum value a la Dave's example (albeit not using Haskell craziness and therefore not nearly as awesome).

I learned a lot about test-designing mistakes from the responses I got. The first problem wasn't clear enough about how I wanted each kind of data represented, which led some people to give superheroes an integer number of powers rather than a list of powers as I'd intended. My fault; I'll do better next time. I also really should've made people write me a third function using map at the end of problem 3; without it students can pursue the "smash two functions together with a cond and switch based an a symbol" method of abstraction and not hit a brick wall at the end that makes them rethink their logic. Also, I awarded way too many points for the bonus. Ten would've been plenty. I will do better on all these fronts in the future.

But overall: the test went great, and I am completely in awe of my class for doing as well as it has. It's only been three weeks since they wrote their first program, and now a test everybody told me was too hard and that makes them come up with their own tree representation and discover map on their own turns out to be too easy for them. If you're one of my students: you rule, a point on which I'll elaborate on Monday. :)

In other news, the programming contest phase 2 starts tomorrow morning. I stayed in the office late working on it (which is why this post is appearing now, quite a bit after worker-bee bedtime). I'm glad I did; I didn't actually do anything useful, but I was convinced that there was a potential bug lurking somewhere nobody else thought there'd be a bug, and due to my insistence two of us made a somewhat complicated test case to find it. That test case proved me wrong, but at the same time exposed another bug that happened to be the very bug that was completely dumbfounding the third member of the team. So, uh, I rule indirectly.

2005-07-07T22:01:00.000-05:00

Today was essentially dedicated to the craft of test-writing, a craft to which I'm not at all accustomed but I found I actually kind of like. I'm glad to report that I'm a perfectly decent Java programmer, at least according to the midterm exam I took for my officemate, who's giving the test to his Java class tomorrow. He, as it turns out, is also a perfectly decent Scheme programmer, though his Scheme is possibly slightly rustier than my Java (I didn't even know that was possible!). My test is going to be pretty tough, I expect, but I think also fair. I'll find out tomorrow, I suppose.

The process of writing a test itself is really difficult, particularly for an intro class midterm — these are people with barely any programming practice at all, essentially anything they could possibly do on paper in any reasonable time looks easy to me. Writing a good intro test, then, seems like a game of extraordinary empathy, where you have to really put yourself in your class's shoes and figure out exactly how much it takes to challenge them but not break their backs. My initial draft was probably on the tough side, and the point weightings for different problems were all over the place, but I think I've rebalanced and tweaked things to the point where the test is probably fair. (Ironically, I made the test easier by approximately doubling the length. That's because I rewrote problems of the form "Do task A" to problems of the form "1. Do subtask X. 2. Do subtask Y. 3. Do subtask Z." Many more pages, but the result is that you don't get hit with one big problem, you get hit with lots of littler problems telling you how to do what you would've had to do anyway.)

In the process of writing the test, I ended up ditching the TeX macros I was writing for the problems in favor a Scheme program that takes a logical test description and spits out LaTeX. It's amazing how much easier it is to generate LaTeX using Scheme programs than it is to generate LaTeX using LaTeX macros. I was able to add quite a bit to what I was able to express and make the code much simpler. (Probably I just don't understand LaTeX very well, but I've been using it for a long while and the Zen that makes everything make sense and work beautifully has not yet hit me.)

Other than that, the only major thing I did was one more revision pass at the programming contest phase two specification; lots of red ink but the spec looks like it's in good shape and hopefully the contestants will like it.

2005-07-06T22:15:00.000-05:00

Today I got to the point in my course when I was finally able to teach my students why you see a big lambda every time you start up DrScheme. As I was explaining it, something clicked for me about why the HTDP curriculum works. As has been said many times before, it's not syntax-based, which is definitely good — you don't want your students thinking that they need a new piece of syntax for every problem or that the kinds of syntax available in language X are somehow a mirror of the kinds of problems in computing. But what's not so obvious is that once you're teaching, you start to realize that it's actually small-step semantics-based. Unlike SICP, which doesn't seem to have much of a unifying pedagogical principle, I've started to realize more and more that the secret weapon of HTDP is that you teach the students a simple algebraic-simplification-based view of program evaluation, and then slowly enrich the set of reduction rules in the language and show them what tricks are possible with those new reductions. That's why the introduction of local (a teaching form for introducing internal definitions) becomes a big deal in HTDP, whereas introducing lambda is not all that big of a deal — local is a new kind of reduction rule that adds definitions to the world; lambda on the other hand just follows the same rules we've been using all along.

That's not to say that students don't still need to practice and struggle with both local and lambda to figure out how they tick; that's more of a pragmatics issue. But as far as explaining them, when you get to lambda, you just say, "Remember our rule for how to simplify named functions? You do that here too." Then you do an example or two, and pretty soon people are able to feed you the right answers when you ask what to do next and they've got their first handholds on a concept that might otherwise be very very difficult to grasp.

I have appreciated the pragmatics of HTDP, in particular the design-recipe idea, for a long time, and I still have to say that the notion that data leads directly to code is a fantastic first lesson in programming that's underappreciated in most curricula and by many professional programmers. But I hadn't until just today appreciated the powerful impact that taking a very careful look at the semantic model you're teaching your students when you introduce them to programming can have.

2005-07-05T20:49:00.000-05:00

After a very relaxing July 4th weekend, my nose was back to the grindstone today as I finally got to some long-overdue PLaneT work. PLaneT is now up to date with the rest of the PLT's infrastructure: the server is using the latest PLT build from subversion, PLaneT's web page uses the new web page look, and most importantly a really longstanding bug in the way archives got unpacked was fixed (in an embarassingly simple way) the result of which is that documentation is properly linked on the PLaneT page again. (I went through and fixed all the old packages that were affected by the bug, too, so the page should now work.)

This smacks of software development to me. I'm not sure whether it's a good or a bad thing that I'm in a research group that does real software development alongside its more academic pursuits: on the one hand, I'm getting lots of experience with real development that I wouldn't get in most places; on the other, every time I spend a half hour tracking down a crash bug that turns out to come from the fact that ImageMagick is installed on my development machine but not my production machine is a half-hour of my life that's not contributing to anything except ulcer development.

2005-06-30T22:29:00.000-05:00

Truly frustrating day today — I spent nearly the whole day trying to get a particular programming thing for the contest working, and couldn't get it working. There is lots and lots of technology in the way at the moment. No fun.

I also started, over the course of yesterday and today, writing up the multilanguage semantics paper after finally deciding that no new actual research was going to be done. What I've got so far is a pretty good picture of how to model the interactions between multiple-language systems, but it is lacking concrete examples of non-lambda-calculus-based languages and it has no large language system worked out. I had initially looked into modelling one of the two popular Java calculi (Featherweight and Classic) connected to a lambda-calculus-based system, but I quickly discovered that even though they are simple for Java models, they are not in any way simple enough that I could actually say interesting things about the embedding without huge extraneous gobs of gibberish about the Java model itself, and that's not something I really care to do. I was also recently pointed to the calculi by Abadi and Cardelli, but I haven't been able to figure them out yet and time is probably a bit too tight if I'm going to submit to POPL.

I definitely want to flesh out an example with OO, and since the author of ProfessorJ is here and recently got an OOPSLA paper about ProfJ/Scheme interoperability accepted, it seems like a perfect fit to try to prove something like soundness for that. But of course I can't do that before the POPL deadline. I think what I've already got now is a good story, and complete in itself, and worth reporting as is, but since I can see all these next steps I can't help but seeing it as a list of things that aren't done yet instead of a list of things I've already done. Oh well, we'll see what they say (if I can even get a draft ready in time!).

2005-06-28T22:29:00.000-05:00

PLaneT is free now. It's no secret that PLaneT's submission mechanism totally blows, and fortunately for me others think this too and decided to help me out. Thanks to them, people may get their packages updated. Thanks.

I spent an inordinate amount of time writing and rewriting the first section of my POPL paper. It is very very hard to get these ideas expressed; I hope they make sense three weeks from now. When I wasn't doing that, I was working on contest stuff and class stuff. Tomorrow we'll be doing the 3D lab.

2005-06-27T18:44:00.000-05:00

Contest phase 1 is over. Running the ICFP contest has been a blast so far; I recommend that you all do it. I was very worried everyone would hate the game, or we'd get no submissions, or whatever, but nothing seriously bad seems to have happened other than (1) a team discovering a degenerate strategy as a result of a dumb last-minute addition we made to the game board and (2) a few tempers flaring over some OS-specific problems (there's a nasty intermittent bug with pipes in Windows that people were getting angry about, apparently).

Now there's just the huge, daunting task of evaluating the submissions, coupled with the huger, daunting-er task of doing this whole thing again, faster.

Bob Harper gave a talk today, and I missed it due to class. He was talking about Twelf; I really wish I'd seen it, Twelf looks like it might be immediately applicable to my work but I can't figure out exactly how it works from glancing over the tutorial.

2005-06-27T18:42:00.000-05:00

2005-06-25T20:40:00.000-05:00

You know what website I really hate? Slashdot.

As you may be aware, we launched the ICFP contest on Friday morning. Before we did, we submitted a story to Slashdot announcing that we'd done so. Very relevant to Slashdot, right? I mean, they've run a story about the contest every year for the past three or four years at least, and for last year's they actually ran three stories (maybe more). So we figured, people will be expecting to hear about it from Slashdot, we'll submit a story about it. We even gave away the contest overview a little bit early to them so that even if it took a while to get posted the information would still be relevant when it was.

Then we waited. 9:00 AM rolled around, and no slashdot. No worries, they're pretty slow with every story anyway, though it sure would've been good to get it on that page Friday morning so all the start-the-workday-with-Slashdot folks would see it (and maybe participate). But whatever, we figured, it'll get posted soon enough.

And we waited some more. We went to lunch. We came back. But every time we checked, the story was still 'pending'. At around 3:00PM or so, right as the workday window was closing, we decided to we should submit something else, shorter and punchier maybe. So we submit another story that points people to the contest, this one carefully edited to fit on the slashdot frontpage, no problem. And we waited some more. Nothing.

Saturday morning, both of us who had submitted stories checked, and both had been rejected during the night. Oh well, we decide, Slashdot must just not be interested in the ICFP contest this year. Its their website, they make the rules.

So now, today, halfway through the contest, they run some random guy's link to the contest web page that's basically the same thing we submitted. Thanks a whole friggin' lot, Slashdot. I guess you do want to run stories about the contest after all, but only after enough time has passed that there's no way anyone reading the article could actually participate in it if they wanted to. You guys are awesome.

Yes I'm grumpy about it.

2005-06-24T21:59:00.000-05:00

Okay, the programming contest is up now. Fun! People all over the world are now (possibly) chuckling at all the stupid little jokes we wrote in and (probably) puzzling their way through the gawdawful rules text that we couldn't figure out how to get rid of. On the plus side, it's now 13 hours in and the worst thing that has happened so far is that there've been some platform-specific problems with the support code we provided and we accidentally let slip that that game had to do with cops and robbers a bit early. Considering that we've been thinking about the game in more or less this form since, um, at least January or so, it's pretty good that we didn't let more than that out. It seems to be pretty well-received, though we're going to have to wait for the submissions to roll in and particularly for the second phase to really see whether we succeeded or not. But for right now, I'm just pleased that things have gone so smoothly — I have to say I was more or less imagining this whole ordeal somehow managing to set all our offices on fire and burn down our building.

In the midst of the contest going up, I also had to teach one of the key HtDP lectures: the dreaded "lists" lecture. Introducing kids to the notion of recursive data structures and recursive functions all in one fell swoop and making it seem natural is a pretty tough trick, and I was definitely not sure I could do it. I eased them into it using a trick I got from Matthew and Robby: you first give a "brain-teaser" of how to store two numbers in a box structure that has a left and a right; then you ask how to store four numbers using boxes (just store two copies of your solution for two numbers); then 8. 16, and so on. Then you ask how to store 5 numbers in a box (make a new box with a number on the left and your 4-number box on the right), then how to do six (repeat the same process), then 7 and so on. Then ask how to store one number, and relatedly how to store zero numbers. At that point, you've developed the idea behind linked lists on the board.

This strategy seemed to work as well as I could've hoped; some people looked kind of blown away, others really took to it, and some people thought it was kind of obvious, but everyone seemed to be able to grasp cons lists by the end of the lecture. We'll see how well they did it when the homeworks come in, of course, but people were answering my questions in class, so that's something.

2005-06-23T22:13:00.000-05:00

What did I do today? You'll find out all about it at 9:00AM tomorrow when the contest starts. As for now, I need to finish up my lecture notes for tomorrow's class - I'm teaching about recursively-defined data and the functions ~~who love them~~ that process them, which is a bit of a doozy considering the relative cakewalk the class has been up until now. I have had very little time to prepare the lecture, though, so let's hope I can make it all sound reasonable tomorrow.

Y'all had better like this damn contest :)

2005-06-22T23:12:00.000-05:00

Fun with exceptions!

How does your favorite foreign function interface deal with exceptions? I'm thinking particularly of the situation where you've got language A, let's say it's Scheme for the sake of argument, and it calls a language B (say Java) with a function argument. Then your language B in the midst of processing calls that function, and that function raises a (Scheme) exception. So what does the FFI do?

The way I see it there are several sane choices.

if any exception would have to "cross FFI lines" — i.e., from Scheme into Java or Java into Scheme — the program just dies. Moby, the language being developed by Kathleen Fisher and John Reppy, does it this way.

say that Scheme exceptions ignore the presence of a foreign function on the stack and propagate up to the next Scheme handler unconditionally. I believe that the PLT Scheme FFI does it this way.

if a Scheme exception reaches an FFI border, the FFI converts it into an "equivalent" Java exception and raises that on the Java side, and similarly if a Java exception reaches the border it is converted into a Scheme exception. This is how SML.NET works.

Are there any other reasonable strategies here I'm missing? There's also the whole complication that if one of your languages doesn't support exceptions (say you're doing a Scheme/C FFI) that you might want to map Scheme exceptions into C error status codes and certain C values into Scheme exceptions.

Anyway. Taught a class today, and did my first lab. It's really hard to come up with four hours' worth of material, but it worked out okay. The lab was pretty fun, and I was pleased that people seemed to be getting the material. It was a simple exercise, but still I was surprised and glad to see the first finishers do the whole thing in just 30 minutes or so.

2005-06-21T22:02:00.000-05:00

Preparing for class took me an amazing amount of time today. I can see why professors complain about teaching — for me, anyway, it seems like I don't have time to do anything else. At the moment the programming contest is only a few days away and the POPL deadline isn't that much further off, so it seems totally extravagant to be planning lectures, but what can I do? It's what they're paying me for.

2005-06-20T20:46:00.000-05:00

So, first day of class today. I was very surprised to discover that there were five women and one man in my class — I don't think there were five woment total in the 30-or-so-person intro class I took back in the day, so it's weird that they were the vast majority. Also, lots of econ majors, but I guess that's to be expected here. Anyway, as to how it went: meh. It's harder when you're on the other side of the blackboard, and though I've thought a lot about what I like in teachers I'm finding that it's really hard to actually make it happen. On my performance: I think I failed to thrill them, and it was like pulling teeth to get anyone to respond when I asked questions, but I don't think I was was super-boring either. The "teaching the experienced" bit turned out to be a basically moot point, since only one person had any serious experience and she didn't seem to have any problem with learning Scheme. I talked for a bit about how when you take English, you're not learning how to speak English, you're learning how to communicate effectively, and in the same sense this class was about teaching you to program effectively regardless of the language you choose to program in. People seemed to respond to that, so I think I'll use it again.

Wednesday is the next class, and due to an unfortunate schedule the (two-hour) lab follows the (two-hour) class after a 30-minute break. I have to keep people absorbing computer science for essentially 4 hours straight. Heaven help me.

By the way, the contest proceeds apace. 9:00AM on Friday I'll have a little heart attack and then I'll do a little dance.

2005-06-18T21:23:00.000-05:00

Ever have one of those days where you start coding something in the morning, and by the time you look around you realize it's after dark? Today was a gorgeous day in Chicago, and at about 8AM I started trying to figure out how to model various exception-handling strategies in a multi-language context; by the time I was done I had four systems in PLT Redex and it was nine o'clock at night. Research is fun! Much more fun than, say, sunlight or social interaction.

2005-06-17T22:27:00.000-05:00

Hard to believe it's Friday. I spent today divided pretty evenly among: 1) secret stuff involving the contest, 2) preparing for my class, and 3) taking stock and a few next directions for the interoperability paper. The secret stuff I obviously can't talk about, and I'd like to hold off on discussing the interoperability stuff for at least a while, but I do have something to say about teaching.

I'm going to be teaching my first intro CS class starting on Monday, and I'm going to do it using the How to Design Programs teaching methodology. This is my first time teaching it myself, but I've been involved in classes that taught that way many times, and while it's amazing how effective it is (particularly since the book lulls you into thinking it's kids' stuff the whole way through) one troubling problem always crops up. Intro classes always have a few people who have done a lot of programming in high school or elsewhere and are taking the intro class even though in their view they don't need to because they feel like they know whatever introductory material you could possibly be teaching already. Maybe they've even got AP tests or chess-playing programs or something that serve as evidence. These people tend to see the HtDP curriculum as a joke - "why are we programming in a goofy language like Scheme, where you can't even assign values to variables and there are no loops and you don't get printf and you've got all these silly parentheses? I wrote a chess player once, I'm obviously a computer genius who ought to be trusted the raw power of do while loops and languages that don't baby you by checking to see if you're writing outside array boundaries!"

The traditional way to deal with these students in the classes I've observed has been essentially to ignore them. The teacher knows best, and students ought to understand that their professors do in fact realize that there exist languages with for loops in them and chose against those languages for a good reason. There are a couple of problems with this tack in my view. First, there's a deeply engrained notion in just about everyone that if you're learning how to program and you're learning language X then you must necessarily be learning how to program IN language X and that any skills you pick up in the process don't apply to languages Y and Z, so it's a waste of time to learn any programming skills in a language you won't be using to write real programs. I've heard this opinion expressed in no uncertain terms by many people with PhDs in computer science, and in fact at my undergraduate university the electrical engineering department used to offer their own intro to programming class specifically because they thought it was a waste of time for their students to learn any language other than C. If it's a majority opinion among PhDs that you can't learn anything useful about programming by studying Scheme, surely we can't blame freshmen for thinking it too. Second, when people who have had a taste of a C-like language see Scheme as it's presented in HtDP, they can't really help but notice that you can't really do anything in it. Sure, we teachers know that they can do everything they need to for us to be able to teach about natural recursion or whatever, but they're thinking "video games! graphics! inline assembly!" and, well, none of the teaching languages anywhere in HtDP let you make any kind of practical program of more than a schoolwork interest. If we don't even tell people that these things are possible, how will they know? And can we blame them for not thinking they're learning anything useful?

I'm not sure exactly what I'd propose to do about it. I think I may have a little spiel at some point in the first class about how computer languages aren't like human languages in some ways, and that the skills you learn in one computer language really do transfer over to others to a much greater degree. I'm also going to try as hard as I can to make homeworks and labs that have students doing things they can imagine really being useful and/or cool, like the 3D lab I did last year that I'm pretty proud of (that was taught in the fourth week of class to people who had no prior programming experience, and most people got the whole thing working!). But I feel like that may not be enough. When I teach this class again in the fall, I'm thinking about making Practical Common Lisp an optional supplementary text and giving people extra credit for doing the practical sections of that book in Scheme (of course I'd have to help them with that, but that's fine with me). That might do it.

Has anyone out there taught a class and figured out a solution to this problem? Or been a student in a class where the teacher solved it particularly well? I'd like to hear about it if so.

2005-06-16T19:48:00.000-05:00

Hi Lambda the Ultimaters! Now that PLDI's over, I'm afraid you're going to have to hear me ramble on dully about my regular job. And since it's mostly about the programming contest you're not even going to get the juicy details. We aim to please, but we miss so often that observers question whether we're even really trying.

I finally explained to a third party what my recent semantics work has been all about. Kathy and Scott from the PLT are in town and Kathy's been working in the same general area as my semantics, so I got out the trusty whiteboard and gamma'ed it up with reduction rules and so on and showed them the overview of everything I've finished up to this point. I was encouraged; they both followed me and seemed to think it was interesting, which gives me hope that the POPL folks will think the same thing. Also, hopefully Kathy will want to take her OOPSLA paper about Scheme and Java and try to prove it sound using our framework. That'd be awesome.

Otherwise: we spent a pretty crazy amount of time working on a new iteration of the LiveCD for the contest, which would probably have been released a few minutes ago were it not for the fact that I forgot to get a list of changed packages and the guy who is in possession of said list currently on a bus headed back up to his Internetless apartment. Oh well, y'all'll live if it doesn't come out until tomorrow.

And naturally there was a lot of crazy hacking and various other work done that I can't really tell you about. Suffice it to say that the bits were a-flyin' at the Worker Bee! headquarters today. We made some progress, but the programming contest starts in 7 and a half days and that's incredibly nerve-wracking to me.

Also planned for my intro to computing class. They're actually going to let me teach over the summer, and it looks like they're even going to give me some students to teach to. I've got seven students enrolled in my class, everywhere from a high-school student to some college juniors. I've never taught a full class solo before, and that's pretty nerve-wracking too.

Man, I will be about 80 times more relaxed by the end of July.

2005-06-15T16:57:00.000-05:00

It's the final day of the Worker Bee! PLDI Roundup! Today had a lot of interesting talks, mainly I think because it focused more on the PLD part and less of the I part. Good stuff.

Invited Talk

The Transactional Manifesto: Software Engineering and Non-Blocking Synchronization
By Maurice Herlihy

As people have been saying for years now, the days of Moore's Law translating directly into faster execution of the same programs are ending. It's not that Moore's Law is over — it doesn't appear to be — it's that the era when cramming more transistors onto a chip actually makes a sequential computation take less time is over, meaning that all the major chip manufacturers are moving towards multicore systems that only make your programs faster if you can keep multiple independent processors busy. However, current parallelism techniques (by which the speaker meant pthreads) are a terrible solution to the concurrency problem and can't scale up to a computing environment in which everyone needs to write multithreaded programs all the time. For instance, he gave a challenge: write a library for a doubly-linked list that allows insertion and deletion from either end, but that allows inserts and deletes from opposite ends to happen concurrently unless that would lead to data corruption (e.g., the queue only has one element or something). After going through all the problems, he concluded that a nice elegant solution to this problem would be a publishable result. The solution to a problem this simple being a publishable result is not a good sign!

He had a vision for overcoming these obstacles, borrowed from the databases community: transactions. The idea is that you send a function that's supposed to be executed atomically to a transaction manager, which executes it and if a problem arises, rolls it back and tries it again. He's implemented a C# library that does this and says that while it's got a lot of problems, it allowed an undergraduate intern to code up a working concurrent red-black-tree implementation in a week — he said he's seen a PhD thesis a pthreads solution to the same problem.

I'm pretty happy with the CML-style concurrency in PLT Scheme, but that's actually more about addressing "concurrency" (= running multiple threads because it models your problem) rather than "parallelism" (= running multiple threads because you want your program to run faster). It seems like a very interesting idea, and I'd be interested to see how far the transactional-memory paradigm can go.

Session 9: Domain-Specific Tools

Programming by Sketching for Bitstreaming Programs
As Simon Peyton-Jones said during Q&A, this seems a bit like magic. You want to make a program that processes a bitstream, taking some input stream and producing an output, for instance dropping every third bit from the input. As it turns out there are several different algorithms for doing this that vary widely in efficiency, and even though what you want can be described concisely the algorithm is far from trivial to implement. So what these folks have done is found a way that you can describe what you want ("drop every third bit") and it'll automatically produce some algorithm for doing it; you can also add in "sketches" that guide how it chooses an algorithm, partial definitions of the algorithm that guide code generation and allow you to tune the output algorithm. For the drop-third program they found that users of their sketching tool made twice as fast algorithms as people writing in C, even when both groups were encouraged to tweak their solutions as much as they wanted to make performance better. It works because bitstream algorithms generally have the property that the goals are much easier to describe than they are to derive efficient algorithms for, but this technique might be applicable to other domains. (This paper shared the best paper award with the one I mentioned on Monday.)

PADS: A domain-specific language for processing ad hoc data
You've got log files in all kinds of ad hoc formats, and if you want to read them programmatically the typical solution is to hack up a custom thing in perl or something. This is a brittle solution, especially if you want to do any kind of error handling. PADS is a language for writing parsers for ad hoc data like this where you describe the file format very naturally -- "there's the string 'FILE' followed by whitespace followed by a number between 0 and 100 followed by ...." and PADS gives you back not just a parser with robust error handling but also a whole suite of fancy tools like an XML converter, statistical analyzer, and so on. The speaker said that their goal was to make the suite of free tools so compelling that people would be crazy not to use PADS if they're doing anything that has to do with ad-hoc data formats.

Composing Security Policies with Polymer
I'm not sure what to think of this. The idea is, you'd rather have security policies be both (a) centralized and (b) composable than the alternative. So, they built a framework of security policies that compose with each other: you have "security events" in your code and then a central security manager that says what to do about it. I could go on, but that's the gist. Here's the thing: security is very tricky, and I'm really uncomfortable using somebody else's security code for my application. I don't know, maybe it's totally benign and really works great, but the road to security breaches is paved with clever ideas about how to avoid having to worry about security.

Formal Loop Merging for Signal Transforms
The actual domain of this work was making a compiler optimization for a specialized signal-processing language so that it could merge loops that go over the same dataset multiple times. I don't know anything about signal processing, so that aspect of the talk went right over my head. However, the way they did it was illuminating: they observed that traditional approaches tried to special-case some particular construct in the source language into a particular object-code result, but that there's a better way to do it. What they did was extended one of the intermediate representations they used so that it explicitly tracked where loops occured, and then made the optimization a very very simple rewrite on that IR. Just that alone was enough to optimize all of the cases those special cases had handled, and several more besides. The moral of the story is that sometimes having the right information in your intermediate representation is very powerful.

Okay, that was PLDI. It was a very good conference, and I met a bunch of cool people and found a bunch of good leads for my current work. And the coveted Worker Bee! Paper-I-Thought-Was-Cool Prize goes to: Garbage Collection Without Paging! The best implementation papers at this conference weren't ones that blew your mind with things you couldn't imagine, but ones that took things that are easy to imagine and proved that they actually work. This one showed that if you puncture the barrier that hides real memory from the memory manager, you have an opportunity to avoid all the performance penalties the OS would otherwise incur. The larger picture it paints is that while abstractions like virtual memory can help us, sometimes they hurt us too by not letting us deal with the messy cases in the right way. In the case of garbage collectors, they hurt us very very much.

Next one of these I do will be for ICFP, I suppose.

2005-06-14T22:16:00.000-05:00

It's Worker Bee! PLDI Roundup, Day 2! My attendence today was less than perfect, so my report here isn't going to be all that complete, but on the plus side they served soft pretzels so that's something.

Session 5: Register Allocation

Register Allocation for Software Pipelined Multi-Dimensional Loops
Differential Register Allocation
Demystifying On-the-fly Spill Code

I missed this session, unfortunately, when I had a flash of insight on how to solve a particular theory problem and spent over an hour writing things on the backs of conference call-for-paper flyers proving a theorem over and over. So, sorry, but if you're trying to allocate registers you're gonna have to look to another weblog.

Session 6: Instrumentation and Testing

Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation
Those wacky Intel folks were out in force today. This was a tool that allows you to write other tools that monitor programs. I have to admit, most of the talks today were very technical in areas I don't really care about all that much, so I didn't really follow them as well as I did yesterday. A lot of people during the Q&A said they really liked Pin, so I guess it's probably awesome.

TraceBack: First Fault Diagnosis by Reconstruction of Distributed Control Flow
This was kind of a compliment to the statistical bug finding talk from yesterday. These people annotate production code with enough information to reconstruct just the control flow that lead to the program's current state when it crashes (though not the values present at each step of computation up to that point). They have a fancy graphical debugger, et cetera along with it it, and they say it works well. During Q&A the speaker indicated that people tend to think not having the values along with control flow will make the reported information useless, but in practice people tend not to need it.

DART: Directed Automated Random Testing
So you want to unit-test some code, but that's a pain. Can the computer do it for you? Yes it can. Say some function takes only "flat" values as inputs (i.e. values that have no particular structure and that you can just pull out of a bag without too many problems). Pick some of them at random and run the function, also watching to see how they were examined by the program (did the function test to see if the number you gave it was greater than 0? That it was less than some global? Et cetera). For every constraint you gather this way, try to find inputs that violate the constraint and see what the program does for those. In that manner you can (at least try to) get complete code coverage rapidly and if there are bugs in any branch you'll find them.

This talk gave me the eeriest feeling that I'd heard it before somewhere, but I couldn't figure out where.

During Q&A the speaker clarified that the program only really works for functions whose inputs are easy to generate randomly. In particular, it doesn't do very well with function pointers because it's hard to pluck those out of the ether.

Session 7: Network Processing

Shangri-La: Achieving High Performance from Compiled Network Applications while Enabling Ease of Programming
Intel again. They introduced a DSL for programming network processors and talked about how to compile that DSL really well.

Automatically Partitioning Packet Processing Applications for Pipelined Architectures
Another talk about parallel processors. This one was kind of the opposite of the first: they took programs that had an explicit processing loop written in standard C and figured out how to chop it into something more parallelizable.

Both these talks are the sort of thing I find it hard to get in to. Sorry if these reports are a bit cursory, but that's the reason.

Programming Ad-Hoc Networks of Mobile and Resource-Constrained Devices
Okay, there are bunches of networkable devices these days: cell phones, PDAs, Game Boys, whatever. You'd like for them all to work together to solve problems, but to do that you need to be able to write programs that will automatically distribute themselves to the nodes on the network that have the resources, even in the face of geographic and power constraints. This work gives some linguistic tools to do that. The coolest part was the example applications: a game of Pac-Man where you and your friends are Pac-Man and the ghosts and you run around an actual physical board with your Palm Pilots tracking which dots you've eaten and whether you've been captured, and the idea of finding your friend at the airport by having every camera-phone simultaneously take a picture and then having some powerful processor do face recognition on each image taken this way. Totally awesome!

Threads

Threads Cannot be Implemented as a Library
Somebody set up us the Boehm! Hans Boehm talked about how you can't design a thread system if the underlying language specification doesn't support it. As an example he "picked on" the pthreads library and concluded that "it is impossible to write portable pthreads code" due to the fact that memory locations are integral to the thread model but undefined by the C standard and various related reasons. Convincing, interesting talk. Read the paper.

Mitosis Compiler: an Infrastructure for Speculative Threading Based on Pre-Computation Slices
This looked like a compiler for chopping up sequential programs into parallel threadable chunks. I skipped out on this talk, unfortunately, so I can't tell you how it went.

2005-06-13T21:36:00.000-05:00

It's the Worker Bee! PLDI Roundup, Day 1! (Yes, the exclamation point is part of the title.) Quick summaries of the PLDI talks.

Session 1: Bug Detection

A Serializability Violation Detector for Shared-Memory Server Programs
The basic idea here is to detect places where multithreaded code should have atomic regions, though it may or may not actually have them, so that a serializability detector can come along and find bugs. All this is done on the fly — serialization violations are only detected post-mortem, but hopefully quick enough to roll back the changes the faulty execution made and then restart that section of code with a coarser thread schedule (or at least alert a human operator). They do this by forming what they call CU's, for computational units, which are sections of code that need to be atomic because (e.g.) they read some data in from a shared variable and use it without reading it again. It's heuristic and based on guessing standard progamming patterns, but it still seemed pretty cool. Someone asked whether the standard programming patterns would be violated because compilers emit optimized and possibly un-paradigmatic code; the speaker said they run on binaries rather than source code already and it doesn't seem to be a problem.

Scalable Statistical Bug Isolation
Take a program, make up a whole bunch of properties that you might want to test (e.g., x < y, f() was called, etc), and scatter them throughout your binary as you compile it. Then when you distibute the code to your users, you get feedback from them automatically in the form of whether these predicates were true or not. Even though each run is only giving you a tiny sliver of information, you can aggregate it all and analyze it statistically to detect bugs -- just find the predicate most likely to predict a crash and from there you can start searching for your culprit. This was very cool research, made more cool by the fact that they found several bugs in real software with it. A questioner asked whether a single predicate was really the best way to find a bug; the speaker responded that in reality they get clusters of predicates that are likely to predict crashes and that in practice they use those.

VYRD: VerifYing Concurrent Programs by Runtime Refinement-Violation Detection
I was out in the hallway for this one, so I can't really say anything about it.

Path Slicing
There are lots of tools that will help you figure out problems given a program trace, and there are lots of tools that will come up with possible program traces that could cause problems. However, those traces might be infeasible, or they might be overly complicated. These guys found a way to improve program traces by eliminating unnecessary junk and possibly refining infeasible traces by finding related but feasible ones.

Session 2: Function Interfaces

Jungloid Mining: Helping to Navigate the API Jungle
I'm in Java and I've got a String object and I want an ParseTree object from it. How do I use the library to make that happen? Can't I just, you know, push a button and make the computer figure out how to get from here to there?

Yes. Yes I can.

This was so awesome.

Checking Type Safety of Foreign Function Calls
I was really interested in this talk. They took the OCaml-to-C foreign function interface, wherein OCaml provides everything as a (mostly) opaque lump into C, and built an inferrer that verifies that the C code does the right thing with those lumps. It was pretty cool, and talking with the speaker after the session I realized that we were looking into very related things. He gave me a really good tip on a paper to read, too.

Session 3: Types

Essential Language Support for Generic Programming
C++ lets you do some "generic programming" by means of template hackery. ML and Haskell also have some stuff like that, but the authors of this paper wanted some stuff from the ML solution, some stuff from the Haskell solution, and they wanted the whole thing to at least look like the C++ solution. So they invented F^G and threw in their laundry list. Someone sitting close to me pointed out that specializing code based solely on the type doesn't work; integers, for instance, form a monoid under both (0,+) and (1,*) and if you've got some Monoid<T> generic object you can only define one or the other.

Semantic Type Qualifiers
You'd like your programming language's type system to be extensible in the sense that you can add your own statically-verifyable constraints and the type checker will make sure they're true. There are many approaches to this already; these guys made another one that seems like it's got a particularly nice syntax and also actually relates the new "types" the user makes up with the program's dynamic semantics, which is cool.

Permission Based Ownership: Encasulating State in Higher-Order Typed Languages
So, if your language has a module system that hides a component's implementation with existential types, your code is encapsulated, right? Wrong! Consider (in Java-ey pseudocode):


class A {
  private int[] ints;
  public int[] bad() { return ints; }
  public int[] good() { return copy(ints); }
}

Since clients could mutate the array that bad() returns to them, they could change A's internal state (even though A objects can only be ascribed type A). The good() function has the exact same type but doesn't suffer from the same problem. Crazy, huh? The paper shows an extension to F_ω that adds ownership types to catch these problems; you say "the world can access the public interface and the public interface can access or update the private implementation, but the world can't update the private implementation" and the type checker makes sure that doesn't ever happen.

The notion that existential types didn't cover the entire problem was a real eye-opener for me, and the talk was worth it for that insight alone.

Session 4: Optimization

Code Placement for Improving Branch Placement Accuracy
The observation is this: branch prediction is very important to the performance of modern CPUs, and said modern CPUs implement branch prediction by storing statistics on each jump instruction in a table somewhere. Alas, the table has limited buckets, so some hashing has to go on, and that hashing is typically on-chip branch predictors suffer from "destructive interference" where one branch is usually taken and some other unrelated branch that happens to get stored in the same bucket is usually not taken. This paper suggests arranging your jumps so that the ones that get stored in the same buckets tend to have the same behavior, and interference is constructive rather than destructive. Great idea, but (a) the microprocessor people aren't telling how they choose those buckets and (b) you can't just arbitrarily move jump instructions around. So the author spent a tremendous amount of time trying to figure out how branch prediction worked on the CPUs he was working with, and got something that gives you a modest performance boost. I can't help but wonder whether all the work will be lost next time a chip comes out.

Optimizing AspectJ
They wanted to make AspectJ faster. They did. I find it hard to get worked up about it.

Automatic Pool Allocation
I really regret that this talk was the one I picked to ignore the first half of while I worked out a problem with the multilanguage stuff that's been bothering me, because from the second half it looked really cool. Anyway, they figured out a way to analyze the program to improve data locality in the heap objects it creates using points-to analysis. Sounds awesome, and it won the best paper award. Question asked: what should programmers do to make sure they can get the benefits of this stuff? Answer: don't use a custom allocator, don't do fancy pointer arithmetic.

Garbage Collection Without Paging
Make the virtual-memory agent in your kernel notify your garbage collector when it wants to page a particular page out, and let your garbage collector either (1) free some memory up in response or (2) nominate an alternate page instead, and you can get a garbage collection algorithm that essentially never pages memory in during collection and thus runs crazily faster than ordinary garbage collectors when memory is tight. Very neat.

Overall an auspicious first day with lots of interesting talks and very little that seemed completely bizarre, incomprehensible, or silly. I am a little put off by the emphasis on quantitative performance gains, but, as Ron Burgundy would say, "When in Rome ..."

2005-06-12T22:31:00.000-05:00

Another Worker Bee! weekend update, this time much shorter: I submitted the Scheme Workshop paper, the revision of which turned out to be not nearly as bad as I'd thought it would be. I also built a codebook for the speed-daters out in HTML -- it's just essentially an XML transformation on the source files that puts the name of the question in the database, its text, its type, and the possible answers. Ought to have been much easier than it was, but then again I knew I'd screwed up the question representation before we even started the study. We'll get it right for the real Topsl.

PLDI tomorrow!

2005-06-11T18:16:00.000-05:00

Special Worker Bee! Weekend Edition! I biked in along the lake-shore path from my Wrigleyville-area apartment to Hyde Park today to accomplish a couple tasks. (I did that bike commute somewhere between 1 and 5 times a week until the weather got really bad last year and as it's gotten warmer I've started up on it again.) We've been having something of a heat wave over the last couple weeks here in Chicago, so the path has been crowded like crazy. Today the season seemed to be conspiring against my commute at nearly every turn: there was a stiff headwind on the way down, not to mention a path full of pedestrians an casual cyclists who weren't really paying a lot of attention to where they were going clogging up the path. On the south side there was some kind of walk against sickle-cell anemia that blocked the entire path several times; I actually had to dodge off the path into the grass at one point to avoid a huge group of people who were just standing there in the middle of the road at one point. And once I got in, my normal route to my building was completely blocked off by (a) cops and (b) a nearly endless line of U of C students who were graduating. Hrmph. (Said graduating students also caused me trouble a few hours later when I was starving to death but couldn''t find a place to eat anywhere that wasn't packed to the gills with grads and their parents.)

Then work: I added one more table to the database the psychologists wanted. My website gathered lots of information about people before the event and after the event, but the psychologists actually had people fill out forms during the event on paper as well, and after they made an excel spreadsheet of the data they had me turn it into another table in the relational database. Not a big deal. I also made an editing pass on what is now the Scheme Workshop paper, basically fixing everything the ICFP editors specifically said they didn't like.

On the way home, more clogged path. Fortunately the stiff headwind on my way in became a strong tailwind on my way back, so I was booking it at like 20mph the whole way. The whole way, that is, except on the half of the path that is remotely close to anything scenic. On those stretches I went like 10mph stuck behind hordes of people who were evidently high or something. Public service announcement: when you are on a bike path, you are on a road. Would you wander around in the middle of a road without paying attention to your surroundings at all? No. So don't do it on a bike path either. Thanks.

The last bit of the return trip was the worst, because I live close enough to Wrigley Field that I'm affected by Cubs traffic (both vehicular and, more problematically, pedestrian). I got home right around the end of today's game. Cubs fans are even worse than pedestrians on the bike path; they walk in giant herds, there are many many more of them, and they're often drunk. Thankfully that was brief, and there were only a couple near misses in the block and a half of heavy Cubs-fans traffic I had to avoid.

2005-06-10T20:49:00.000-05:00

Though I generally don't pay much attention to this sort of thing, the end of the school year is here and it's now technically summer session. Whatever, it doesn't really affect me too much except that there are fewer people around and this year I'm teaching my first course. But this year several people are leaving, so it's a little more significant to me. Goodbye Dave! Goodbye (for the summer) Jon! Goodbye (in a few months) Jake and Don!

PLDI starts on Monday. The programming contest starts in two weeks. My class starts the following Monday. The second phase of the contest goes out two weeks from then, and then the POPL deadline is upon us. Not really much like the summers I used to have when I was in high school.

2005-06-09T17:09:00.000-05:00

I've been home sick today, and for whatever reason I couldn't stop thinking about PLT Scheme as a language for getting work done. I know that recently my research has been mostly theoretical, but I'm not actually much into that stuff — I'm much more interested in implementation. And as I've written more and more software in PLT Scheme, I think I've decided that I'm not a fan of its being untyped, as I think I've said; I really want static guarantees of correctness and I'm probably willing to deal with the occasional hacking around an artificial type shell game to get them (I'm thinking here of SML's system-interface libraries mostly). On the other hand, the ability to get complicated tree-structured data like XHTML without having to explicitly describe its shape first is useful.

But I'm not sure whether that's really appropriate for software that needs to be relied on; sure, unit tests are supposed to catch everything that type errors catch, but when you're coding at 100 miles an hour trying to get a feature done before tomorrow you'd really rather have it be caught before then. Also I can say from experience that taking a program written that way and releasing it to the world is an absolutely nerve-wracking experience no matter how much you've tested the code beforehand. (As it happens, I discovered exactly one type error on the speeddating site "in the wild"; in some cases I stuck something that wasn't supposed to be there onto an obscure error page that I'd forgotten to test. It affected a couple people before I fixed it.)

That said, I'm not really sure what the best alternative is. Whether it's purely an accident of history or not, the best web programming system I know of relies on Scheme and the typed alternatives seem pretty bad by comparison (with the exception of Haskell's WASH, though I like the Scheme server better). Maybe someone's doing something like the PLT server for OCaml -- that would be kind of exciting, actually, I really want to do some work with OCaml.

There are tremendous problems with web development in Scheme, some of which are shared by other functional languages (popular servers will cause resource-utilization issues eventually, but it's harder to get rid of them in languages that attempt to abstract all that stuff away than languages that put it in your face) and some of which aren't (PLT's database support still sucks and still needs to be improved dramatically --- another nerve-wracking part of launching the speed-dating site was that I was using a postgres driver I had no reason to trust with heavy load, though it turned out to work fine). But the killer language that would make me switch probably hasn't been invented yet. Maybe Links is what I want? I hope so.

2005-06-08T08:20:00.000-05:00

You might have noticed that I stopped posting things here sometime last week, despite my ostensible goal of posting something every work day. That's because I finally got tired of writing entries that basically said "I can't say anything about what I did today"; pretty much my whole academic experience for the past week has been programming contest related and there was nothing much to say.

But yesterday I actually did pick back up on some non-contest-related stuff, so I ought to mention that. My paper for ICFP that got rejected was semantics for Scheme, and it was rejected basically because the reviewers thought it wasn't interesting to the larger ICFP audience. That may or may not be true, but it will certainly be interesting to the Scheme community, so we're incorporating the reviewers' suggestions into our draft and sending the result to the Scheme Workshop. That's what I did for a fair bit of yesterday, along with moving a little closer in my understanding of the weirdness that is theoretical work on foreign-function interfaces (I'm about ready to make the claim that particular embeddings give you isorecursive types, which is kind of neat). As the POPL deadline approaches, I'm realizing that a big system with Java or something like that embedded may not be ready on time, but I think I'm going to write up what I've got anyway.

Also yesterday was some database monkey work that will find its way in some form into Topsl. It's great that so many people seem interested in it. I really want to get a real thing out the door; I think it has the potential to be huge.

2005-06-01T20:54:00.000-05:00

Much discussion was had on our mailing list that stemmed from misunderstandings of what our LiveCD was for and who could compete in what; in response I wrote up a FAQ and added it to the contest web page. Again, that's about the only public bit of knowledge I can report.

Yes, I do regret my poor timing in launching this particular writing endeavor precisely at the moment when I can't say anything about what I'm currently doing.

2005-05-31T19:32:00.000-05:00

Well, the contest web page is finally up. This is one of a few different contest-related projects I've been working on, so I'm glad I can finally start talking about it. Check it out: there's a mailing list you might want to subscribe to and a bootable linux CD you might want to download if you're interested in competing when the contest starts at the end of the month. We've been Slashdotted about it, which is neat. I don't think I've ever been Slashdotted before.

Other than that, meetings and writing and stuff like that. Oh, I officially heard back about the ICFP paper; we got rejected. We'll submit it to the Scheme Workshop instead, and it's probably a better fit there anyway.

2005-05-27T23:02:00.000-05:00

Messed around with bootable Linux CDs. Prepared web pages for release. Messed around with BitTorrent. Basically, today I played IT worker except I also did a lot of game design. At this point "design" isn't quite the right word, it's all just about tweaking the wordings of things and arguing the finer points of various corner cases and so on. It's more like development, and even more like polish.

It's amazing how very slowly things seem to go when it actually matters that you not screw up.

2005-05-26T23:51:00.000-05:00

More secret stuff, punctuated by a couple speeddating crises in which the psychologists thought a particular important question that was first presented today was saving incorrectly, but it turns out that the first three people who answered it were just weirdos who didn't want to fill out that question for whatever reason.

I promise these things will get more interesting once the programming contest starts and I can talk about it.

2005-05-25T22:26:00.000-05:00

There's really not much I can say about Wednesday. The programming competition is consuming an increasing portion of my work time, but obviously I can't tell you what I'm doing. I think Thursday or Friday there may be some news to announce, but I really don't even know whether that'll come to pass or not. So I guess the only thing I'll say is that I spent about 30 minutes and added a feature to the speed-daters web site after realizing that the deadline by which it needed to be in live use was, um, tomorrow. It was no big deal, but still it was annoying.

I'm growing less and less enamored of Scheme's untypedness. Even contracts can't help you in some situations, because values don't have principal types: I was in a situation where I wanted to extract an element from a list using Scheme's assoc function. assoc, if it had a type, would have type α * (listof (cons α β)) -> (union (cons α β) #f). It takes a value and a list of pairs and returns the pair in that list whose first element is the given value, or #f if there is none. You'd imagine that you could write a contract that would enforce the same behavior, but you can't: if someone gives you a string and a list of pairs whose first elements are all symbols, how do you know the set the programmer was thinking of wasn't the union of the set of strings and the set of symbols? Or that particular string and those particular symbols? Or maybe the set of all those particular symbols except one, in which case the contract should alert you that it's been violated? The solution is just not to use this kind of polymorphism in contracts, and if you know more about a particular call-site then make a specialized function with the contract there. But that's obviously a pain.

I think I may be coming around to the opinion that my ideal language would have a static type system with an explicit mechanism for allowing you to turn it off, or allow you to run code even if there's a type error somewhere. Basically the way you used to be able to do with MrSpidey in DrScheme; write some code, typecheck, fix every error it finds or come up with a justification for why it's not actually an error, repeat.

2005-05-24T19:29:00.000-05:00

Three things.

I worked on secret stuff for most of the day. At least some of the secret stuff I've been working on ought to be unveilable very soon; that'll be a big weight off my shoulders. The ICFP contest initial start time gives us four and a half weeks to sort out everything. That'll be a relief.

I went to see a talk today by Derek about recursive abstract datatypes. It was interesting. I talked with Dave about the multilanguage stuff; he's interested in the project, so I'll probably give him a more thorough talk about it next week. Hopefully he can give me a little more insight into the interesting type system issues I could address — he already gave me two without even thinking about it, actually.

I looked into doing pivoting on a PostgreSQL database as a part of the speed dating project. I had hoped it could be done in-engine, like you can do with Access databases; it turns out that's not really true but you can pretty easily write scripts to do it if need be. That wouldn't really work too well if I needed to have data flowing into the database at the same time we were analyzing it, but I don't so this'll work. I understand that normally pivoting isn't necessary, but in my case I don't really see a way around it, so I really do wonder whether my situation is one that just can't be handled with standard database stuff.

2005-05-23T20:48:00.000-05:00

I am having the hardest time finishing off this one system for the multilanguage paper. Every time I think I've finally got it done, I realize that I should've arranged something differently, or I need another nontrivial lemma to establish that something holds, or my induction doesn't really work, or whatever. And by the time I'm done, the goal is to make it look obvious enough that people's eyes will glide right over it without even having to pause. I'm beginning to fully appreciate Pierce's quote about how the proofs are almost always boring if the definitions are correct, but the definitions are almost always incorrect.

2005-05-20T18:27:00.000-05:00

In the morning, much work was done on the multilanguage system I've been working on, and it's now just about done. Which is good, I've got a lot more I want to do with the framework I'm developing, so it's good to be making progress. After that, some work was done on the paper response; we worked with renewed vigor today after learning there is a slim chance the paper will still get in, and also because of our sense that some of the reviewers' misconceptions can be cleared up with just a few words of explanation. Things are still looking pretty bad for the forces of rad, but we've got at least one person weakly in our corner and another person who we might be able to nudge over into friendly territory.

Finally, some work was done on the contest. You'll have to wait for that one.

2005-05-19T22:56:00.000-05:00

That certainly sucked.

So today — I'm sounding like a broken record — I mostly worked on secret stuff regarding the contest and doing a proof of something. I actually made quite a bit of progress, but the report would be pretty boring. Wait for my paper, it'll be good.

Anyway, the most important thing was that at 5 I got preliminary, we-get-48-hours-to-respond-type reviews for the paper Robby and I submitted back in April. It did not go well. The reviews were, um, mixed, including some good stuff and some stuff that seemed almost deliberately insulting (I shouldn't get into more detail here). But overall, the reviewers weren't very impressed. Damn. I could say that I had never thought the paper was a good fit for the conference, and I have documentation proving that's true, but it still sucks to get bad reviews.

2005-05-18T07:17:00.000-05:00

Big two-day update!

Though I haven't been working like a fiend, I have found myself for two days in a row working from the early hours into the late; that has cut into my Worker Bee! updating time, alas.

On Tuesday, I spent the morning installing Gentoo for a particular purpose. Gentoo I feel like is more than a little absurd as a concept, but the installation guide at least is pretty thorough and if you're willing to think about what you're doing isn't too bad to get working. The afternoon was all spent doing secret stuff for the programming contest, which was fun and is progressing nicely.

After work, I had to get home quickly because I had a meeting with the psychologists about the speed-dating project. It occurs to me that I may never have explained what the speed-dating project is, so I suppose I ought to do that before I continue: during my first year as a graduate student, I had a friend doing a PhD in psychology at Northwestern, which is also in Chicago. There was at the time a new faculty member there who had planned a big year-long longitudinal study that had an essential web component, and he found that due to a particular methodological twist he wanted it was impossible to find anyone who could write the web part for him. Said new faculty member was banging his head against a wall and about to give up on the whole project when he happened to ask my friend whether she knew anybody who wanted to do psychology programming on the web for cheap. She knew that this is an issue I've been interested in ever since undergrad, so she gave him my name, he called me, I roped in a friend of mine and long story short we made him a web site. We even wrote a little paper about it afterwards.

Now we go to February of this year. Psychologist wants to do another online study, and since the first one went so well with me he writes me and asks me again. This one is about speed dating; he wants to study people's initial attraction to each other and he thinks a speed-dating type event is a great way to get people interested in participating and generating the reams and reams of data he'd want to collect from them. Speed dating generally has web site support and his study will definitely need a lot of it, so he asks me. I'm intrigued, I'm interested in exercising my web programming muscles again, and so I say what the heck.

The speed dating site turned out to be intensely more complicated than the first study was, and I was doing this one myself so it was a pretty major task. But I ended up making it work, and 160 little speeddaters used my software and 7 speed-dating events went off with -- well, not without a hitch, but with few enough hitches that it certainly seems like a success rather than a failure. The study's not done yet, but all that's left now is the speeddaters come to the website every 3 days and answer some tracking questions; they'll do that for the next couple weeks and then the whole thing will be over.

So Tuesday night I met with the psychologist and his grad student (who actually was the leader of this particular research project). I did this for free in exchange for a co-authorship on the paper, but I think they feel like I got a raw deal (I don't think that myself, incidentally) and they ended up buying a Cuisinart fancy food processor and a digital cooking scale as a thank-you present. Woot! Thanks guys!

Then we spent the evening talking about two things: firstly, they are somewhat interested in turning the speed-dating thing into a product we could sell. Second, the data had to be stored into a relational database this time, and they understand why that's good but have no clue how to write queries sophisticated enough to answer their questions. I'll need to either teach them or do the queries myself. Maybe there's some magic report-writer software out there that'll let them do all the queries they want without having to know any appreciable sql? There are lots of fancy things necessary for this data, though; things like self-joins and and left joins and aggregation and sql builtin functions and so on. The meeting broke up around 10PM.

So that's Tuesday. Today was spent basically worrying about my ICFP submission, the reviews for which I will get to see on Friday but had hoped maybe would magically get sent out two days early (they weren't). I also spent a lot of time working on doing a more proper job typesetting some of the multilanguage stuff and doing some proof stuff; I'm going really slowly on it, I fear, because the straight-ahead inductive proof misses the elegance of the model and thus I fear misses an important opportunity to avoid re-establishing things we already know to be true. (This is difficult to talk about without explaining everything; if you see me in person and you care, ask me and I'll explain it further.)

I did discover several things; among the most interesting was whizzytex, an incremental LaTeX viewer as an Emacs minor mode. From those ever-impressive French hackers at INRIA. They point out that it works best with Active-DVI, an allegedly-superior xdvi replacement also out of INRIA and written entirely in OCaml. I really need to learn OCaml one of these days. I've heard it called "the Common Lisp of ML" where that phrase was intended as a pejorative, but as I program more and more I think I've decided there's an important place for the world's Common Lisps.

Then tonight I called up my friend who worked with me on the original psychology study, who now lives in Boston and with whom I hadn't talked in at least a couple months or so. I told him about what I'm doing, and he had yet another possible application for the multilanguage research I'm doing — I tell you, everywhere I look there's somebody else with some problem I think my system could solve, I'm really thrilled about it. Then we talked for a very long time about making a viable, potentially commercial version of the system we've been talking about since the original psychology study. He's interested in going for it, especially if there's actual money involved. That's great; I'm not sure I'll be able to join the business venture myself, at least not until I get my PhD, but since everyone else seems willing and able to start on it right away I think it'd be foolish for them to wait on me. I really hope we can get something good running, though, I think the social science world can really use this sort of thing.

Things are looking pretty exciting on that front. Right now, though, the most important thing is for me to stay on target research-wise, so that's what I'm going to do.

2005-05-16T21:08:00.000-05:00

So last night I submitted a paper review. This morning was dedicated to patching that review after I realized there was a small but significant bug. Thanks to the journal's editor for being understanding and holding off on mailing out the review until I was able to fix it up.

After that there was a little working on the semantics stuff. I finally got organized enough to make a list of the results I've proven and the directions I want to pursue. I also got started on an important proof, though I didn't really get anywhere much, because I actually spent quite a bit of time working with our contest beta-testers handling issues in person and over the mailing lists. I ended up spending entirely too long writing a program to perform what ought to be a trivial Unix task; I wish I could say what it was but I'm afraid if I told you what it was you'd figure out the whole darned contest and that would be totally unfair. We certainly wouldn't want that.

But all that got interrupted when my Amazon shipment came in. Barendregt, Essentials of Programming Languages, and Lisp in Small Pieces. All classics, and I've read none of them. It turns out that none of them are really for skimming either, so I started in on Barendregt at school and brought EoPL home with me. EoPL is certainly less dense than Barendregt, but I'm worried that if I were to teach it I'd end up assigning way too much to my students because everything I've read so far seems like it couldn't possibly take any time. Honestly, I don't in my gut think it'd be unreasonable to assign all of chapter one including every problem in between, say, a Thursday and a Tuesday class session, though I know intellectually that's not reasonable for the kids. But it does seem great.

Question: EoPL seems like it'd be a good intro book focusing on interpreters and dynamic semantics; Pierce's Types and Programming Languages is great for teaching type systems. Are there comparable books for teaching compilers in a functional context? I know of Appel's Modern Compiler Implementation in ML, but I'm not wild about it (and it doesn't even really talk about implementing functional features until the end anyway). Anything else out there?

2005-05-13T21:36:00.000-05:00

Good progress today on a couple fronts. First: I spent some time trying to pin down the problem I was talking about yesterday, and realized that the real problem was that I was being naive in the way I distributed guards across functions. If you track who's asking, i.e. whether you're guarding an ML value from Scheme or a Scheme value from ML, everything works out. It's actually just like how blame-tracking works with contracts. Very cool.

I also sent the task for the contest to the beta testers. The fun begins now as people's problems are starting to roll in (it's weird, for instance, how few people know what an HP48G is). After that we had the contest meeting, which was actually unusually productive. And it seems to have spawned a big email discussion, which is good.

Now the weekend, which will probably be at least partially for work.

2005-05-12T18:24:00.000-05:00

Lots of little things today. I actually didn't end up doing that much, but I got little pieces of lots of things to happen.

The morning was essentially for the programming contest spec. Another draft out the door, more revisions, et cetera. I also spent a good chunk of the afternoon doing the same thing. It's surprising in a technical specification how difficult it is to make everything work out, how many tiny things there are that have to be right or else the document doesn't work. Makes it a big pain to get these things right.

Also today the guy who maintains the PLT Scheme web pages did a new revision of the code that generates HTML. Since I control the PLaneT page, that means I need to propagate the updates there.

After I found out about that, I started up on the declarative images and 3D anaglyphs paper I was talking about yesterday. After about a paragraph and a half, I ran into Robby and he said he thought it'd be better to scrap the whole thing to focus more on the foreign interface semantics. I'm kind of glad of that, actually. I tend to sign myself up for too much, and while this wasn't a lot it isn't like I have nothing to do.

So when that was done I worked on the multilanguage semantics stuff. Robby thought that the right way to represent the dynamic checks you need to guarantee type soundness was as guard functions that get distributed just like contracts. I worked that out, and actually I'm not sure that works well -- the thing is, exactly what needs to be checked, if anything, depends on the reason the conversion is being performed, and that information isn't known if you separate the dynamic checking out from the conversion process ... I think. On the other hand, having the dynamic check separate from the translation is useful to a major theorem I want to prove, so I did a version where the mapping functions introduce guards but those guards are represented separately. The guards don't distribute, though: they're just straight up projections. Probably you could show that guard composed with translate composed with translate back is a retract or something, I dunno, sounds plausible. We'll see.

In other news, I'm a big nerd. I got my tax refund and decided to spend it on a few expensive computer books I've wanted for a long time. So now, coming to my office courtesy of Amazon: The Lambda Calculus, one of the few books important enough to be known by the last name of its author, Essentials of Programming Languages, and Lisp in Small Pieces. I've wanted all of these books for a long time, so I'm glad to be getting them. Thanks Uncle Sam!

2005-05-11T19:20:00.000-05:00

In the morning I fixed a minor speed-dating crisis, but otherwise today was spent almost entirely on super-secret stuff. I released a draft of the spec to the committee by 11:30 and then went to the thesis defense of the guy who works in the office next to me. When I got back I had plenty of feedback, and I spent the rest of the day incorporating it. Afterwards there was another release, and then I went home.

Sorry, not much more can be said about that.

I'm trying to make up my mind about whether or not I absolutely hate LaTeX or just mostly hate LaTeX. It's the epitome of the whole Unix aesthetic: everything is doable, but nothing is easy. I frequently get upset about things like changing margins or dealing with stupid figure problems, but on the other hand you can define macros and at least somehow get the abstraction you want. The rules for what works where and what affects what seem byzantine to me, though, so my abstractions are a lot less abstract than I'd like, but I'm not sure whether that's me or it. Probably both.

2005-05-10T22:44:00.000-05:00

Mostly a collapsing day, which is not my favorite kind. In the morning I tried to update my reduction systems for the multilanguage semantics work I'm doing so they were arranged in a new way that facilitates a really nifty connection between this work and Robby's contracts. COLLAPSE! Turns out that broke everything; while it's still possible to do it, it's going to be much more involved than it was supposed to be. Then I worked on the programming contest some; and as I checked the old tasks for some inspiration I noticed something odd: our task was by far the largest that had ever been published. COLLAPSE! I went into a revising frenzy trying to reduce it, and when I did, DOUBLE-COLLAPSE! I accidentally dropped some important stuff and I'm going to have to make sure I've fixed all that today.

After that was the contest organizational meeting, and then for some reason that now escapes me I signed up to write a small paper for [FDPE '05 http://www.cs.kent.ac.uk/people/staff/sjt/fdpe05/] about the [3D lab http://people.cs.uchicago.edu/~jacobm/151-lab/lab4.html] I designed last year and the image.ss teachpack that makes it work. Only 5 pages, due in 3 weeks. But unfortunately it seems like the paper may focus much more on the teachpack, which I didn't write, than the lab, which I did. Oh well. The conference is colocated with ICFP, to which I'm going anyway, so it seems like submitting something is in order.

Then I biked on home and after literally collapsing and then recovering, I checked my email. COLLAPSE! Something mysterious was wrong with the PLaneT code; new versions hung when they were supposed to be downloading from the server. COLLAPSE #2! There was a huge problem with the speed-dating site: on the followup, on the _one_ page where I wrote the questions directly I'd missed a couple. As it happens, those questions were apparently critical to the entire endeavor so I had to do some speed-coding to fix it.

Reasonably hectic. But the weather was gorgeous.

2005-05-09T22:01:00.000-05:00

Just a few things today.

I finally set up automatic nightly backups for the speeddating site. Cron is really a cool tool, I have to say, though I also have to say the interface kinda blows. It's really magical the first time you get an email from cron telling you about successful completion of some job you'd forgotten you scheduled. Pretty neat.

After that I dug up a bunch of the multi-language semantics stuff, brought it up-to-date with the new version of Redex, and got a simply-typed lambda-calculus embedded in an untyped-lambda calculus system working. That system, as it turns out, is pretty cool: you actually end up getting higher-order contracts in the Findler and Felleisen sense for free out of the embedding. After I'm done demonstrating that result a bit more formally, I'm going to show that embedding simply-typed lambda calculus onto itself can actually give you a language that's not strictly normalizing. Then there's a couple proofs, and then the big task of modelling and then proving correct a large system. This research is turning awesome everywhere I'm looking. Yay.

I read up on Reynold's separation logic for the PL reading group meeting. Nobody really understood the paper very well, but it seems very interesting nonetheless. We're reading about it again next time.

And some other stuff not really to be shared.

2005-05-06T16:21:00.000-05:00

Unlike the rest of the days this past week, today I pretty much did one thing all day: worked on the ICFP contest. It's dawning on me now that as the ICFP contest is sort of a secret, its ascending importance to my average workday may have a serious negative impact on my Worker Bee! reporting. So I'll tell you all the banal details, but not anything significant. To whit: I spent most of the morning munging HTML files into LaTeX files, as I did yesterday. After that was done, I spent some more time copyediting and bringing my horribly deficient TeX skills up to speed. After that there were some substantive content changes, followed by fast 'n' furious office-equipment usage section and a meeting at 3:00.

The point of all this is that we're going to be having a dry run of the contest in the next week, and at this point we need to be ready for it. So we work.

Hm. I don't think I can tell you much more than that.

On the Speed-Dating front: multiple transgressions per person need to be implemented. That is the absolute last thing. In 40 minutes the last kids will roll over into followup mode, and at that point we'll be completely done with 2/3rds of the code I wrote for this project. Weird.

2005-05-05T22:35:00.000-05:00

It appears as though people are paying attention to the speed dating study, much more than they did to the freshman dating study of a couple years ago. That article is actually the second that ran in the Daily Northwestern about our little project; the first was some guy's column. It was funnier, though this one was more informative about what the project is actually about. Reading these articles it becomes clear exactly how weird my own perspective on the project is: as far as I'm concerned, the actual speedily-dating-people part of the project is pretty much incidental, just a way of knowing when to roll events over into new phases.

Actually, as of last night all the speed dating is over, and as of tonight every match has been announced. Tomorrow at 5 the last group of daters will get rolled into the followup, and then the project will be all over but the data collectin'. The problem with real data collection is mostly that people want to do weird things that totally screw up your nice models; no you can't fill out the intake survey after you do your matches because I didn't think of that and it doesn't make any sense anyway. Computers don't allow you to bend the rules and neither do I. Hrmph. (We've had to deal with a couple rule-benders. It's been annoying.)

On an unrelated note: how cool is this? In SLIME, as in DrScheme, esc-p in the REPL pulls up the previous expression you evaluated. BUT: in SLIME, if you've already typed something at the REPL (without evaluating it), you get taken to the previous expression THAT STARTED THAT WAY. Awesome! It wins one point. I looked into adding that to DrScheme, but couldn't figure out how to do it in 30 minutes or less so I gave up. But it'd still be cool.

I then spent the next many hours trying to convert our programming contest documentation from HTML, which for some reason I thought would be a good first draft format, to LaTeX. Didn't finish. Without being too specific, there are lots of diagrams, and it turns out to be a big pain to get everything from a PRE tag looking okay when typeset. I developed some perl and Scheme helper programs and found somebody's precooked binary to do the conversion, but it was still lots of work. Moral of the story: for all its faults, LaTeX has enough meta-information in it to make it a good document format for converting to others. HTML has no such property. So make your documents be LaTeX by default.

That's pretty much the size of what I did today, other than talking for a while about the status of the multilanguage semantics work (we've solidified a direction) and managing to totally embarassingly screw up deployment of the feature I wrote for the speedy daters yesterday (forgot to copy a file, server yelled when people tried to fill out their survey).

After I got home, I installed OS X Tiger and started playing with Dashboard widgets. I'm totally going to make a MzScheme or MrEd REPL widget. Totally.

2005-05-04T20:28:00.000-05:00

"If you define a program, then highlight it, then right click the mouse one of the options is collapse SEXpression. You have no idea how funny 9th graders think this is."

That's a bug report from this afternoon, just before I went home. The SEXpressions were a-flyin' today, too, metaphorically if not literally. For one thing, Robby got back from Taiwan after a two-and-a-half-week trip. The practical upshot of which was not too much, I wasn't waiting on him for anything, but it does mean I ought to get started prepping my class for the summer quarter.

Robby came by in the morning. After we talked, I had a little work to do on the speed dating site: seems people are having "no relationship" with far too many people, the result of which was that people were answering like two questions per followup and being on their merry way. We have a solution, which was to ask people to give the names of other people they may be seeing until they've filled up four slots (or they run out of relationships total). Lucky for me, I'd already written most of the code before. So this new feature was a quickie. It gets launched tonight pending a few more changes the psychologists told me about over the phone a little while back.

There was a dissertation defense at 3 I wanted to see, so I had an abbreviated workday. I only did one other major thing, which was reading over a paper I'm reviewing. I've read the paper over before, but it's both long and difficult and even after reading it over again I don't really understand it. That blew a few hours, though.

I did a bunch of little stuff too, nothing major. Added a few packages to PLaneT, though Jay tells me he's writing a package-upload client so I won't have to do this much longer. A little chatter on one of my mailing lists inspired me to share the read-all-sexps trick Robby once showed me: to read every S-expression out of a given port as a list, the trick is to make a fake port that consists of an open paren, the original port, and a close paren; then you can read one S-expression out of that fake port. About 10 times faster than just reading expressions one at a time. Strange but true!

I also may have fixed a couple of very small but (at least in one case) extremely annoying PLaneT bugs. It has to do with the installer, though, so I'll have to wait for the nightly build before I can test it.

Afterwards, dissertation defense. Defense-tastic, that's all I'm going to say about that.

Okay, time to fix the speed daters.