Thursday, October 14, 2010

Type Inference, In and Out of Context

Our reading group read the 2010 MSFP paper Type Inference In Context by Adam Gundry, Conor McBride, and James McKinna (ACM link). This was mostly because not all of us went to ICFP and not all of us that went to ICFP saw that MSFP talk (I was at HLPP and others were at WMM, IIRC man there are lots of acronyms in this sentence.)

Anyway, the people that went to the MSFP talk really liked the talk, so we read the paper. Some of it was confusing because state monad is not my native language. To understand it better, I re-implemented it in ML after the reading group. William and I then got into a discussion about how he had written a trying-to-be-very-clean implementation of the imperative type inference algorithm for MinML, so I adapted the algorithm further to the larger MinML language, and then adapted Williams code so that it ran in parallel with mine. And then I decided I wanted to throw the whole thing on my door as a parallel-corpus sort of thing.

The result is an impossibly sized PDF poster that I can turn into 6 tabloid sheets and put on my door, titled "Type Inference, In & Out of Context." It isn't aimed at being particularly introductory, but if you have read the MSFP paper it may be helpful as a guide to ML transfer, and I found the comparison to the imperative version of type inference quite enlightening.

There's a secondary interesting question here: what are good ways to present large pieces of literate code for dissemination? I kind of like this narrated poster form, especially for parallel corpuses, and I like literate Twelf things like the page on lax logic, but because I haven't had a lot of feedback and haven't been a reader of a lot of these sorts of things, I don't know how good I am at pulling it off. I'd appreciate feedback!

[Update Nov 18, 2010] Michael Sullivan notes that one aspect of "good ways to present large pieces of literate code" is actually providing the code so it doesn't have to be ineffectually cut and pasted from a pdf. The code is available in three files: typebase.sml (the language definition, snoc lists, and cons lists), typenoctx.sml (the imperative algorithm), and typeinctx.sml (the pure algorithm).

No comments:

Post a Comment