« October 2008 | Main | May 2009 »
I'm writing a thesis; parts of it are a big mess just now & I spend a lot of time stuck and wondering what to do next.
So today I reached for an Oblique Strategy and got this:
Look closely at the most embarrassing details & amplify them.
So that's what I'm doing tonight: making it messier.
What I find interesting in the above story of the origins of SOS is, on the one hand, how complex the various influences on ideas are and, on the other hand, even if the ideas themselves are simple, how much work one needs to do to show their power. I would expect that in this respect the story of the development of SOS is quite typical. Another interesting aspect is the mutual influence of teaching and research: things need to be simple so they can be taught to students who do not know strange calculi, and they need to be comprehensive to convince them; pleasingly, these qualities are also what are needed scientifically.[UPDATE: Link corrected, thanks Ohad.]
Last week we had some really cool guys come visit us from Germany: Torsten Grust and Tom Schreiber of Universität Tübingen. I was aware of Grust's work on functional database query languages from some years ago, but was surprised when he emailed us (the Links team) and let us know about their new work with Ferry [1], essentially a nice, first-order, functional programming language which they compile to bundles of SQL queries.
This overlaps a lot with what I've been doing with compiling Links to SQL. I had recently discovered a way of compiling expressions in a pure, non-recursive, higher-order fragment of Links to single SQL queries, given the condition that the source expression has the same type as an SQL query: a multiset of tuples of base type.
What Torsten and Tom have figured out how to do is to compile expressions of nested data type to a small set of queries having flat type, such that you can easily assemble the nested result from the flat queries. This is something I had thought about how to do and hadn't cracked, so I was very pleased when the Tübingen guys turned up with a way to do it. In fact Jan Van den Bussche had figured out a similar encoding (of nested to flat algebra) in 2001 [2], in a purely theoretical setting and with (unordered) sets as the only container type. Torsten and Tom can actually handle unordered bags and ordered lists, which is another big step forward.
Their work and my work overlap, but we each had things that the other didn't have. They had nested data structures and ordered collections (lists), while my compilation works for a higher-order language, where functions are first-class values. Also I'm working in the setting of an impure language with side-effects; we can statically identify database-compilable expressions, which must be pure, by using a type-and-effect analysis. The two systems seem to fit together very well, and we're looking at integrating them.
Torsten, and Tom, and myself, Phil and Sam had a nice visit together in Edinburgh were we pried into the details. Three cheers for collaborative visits!
[1] "Ferry: Database-Supported Program Execution." Torsten Grust, Manuel Mayr, Jan Rittinger, Tom Schreiber. Proc. 28th ACM SIGMOD Int'l Conference on Management of Data (SIGMOD 2009), June 2009. To appear.
[2] "Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions." Jan Van den Bussche. Theoretical Computer Science, 254(1-2). p. 363-377. 2001.
(burp) OK. In my defense, there was a spectacular hack which meant I had to switch off all the active junk on this web server and live off static content for a while. That added to my resistance to keeping the blog up to date. But now I'm back and ready to rock. End hiatus now.