Geeky things and other research from a work in progress

2009-09-30

"Extensibility and type safety in formatting: the design of xformat" at the Dutch HUG

I'm finally getting around to posting the slides for my talk at the Dutch HUG on 11 September. After that, I was preparing my talk for IFL on incrementalization of datatype-centric programs. I arrived back in Utrecht yesterday morning and crashed mid-day.

You can find the slides on Scribd and on Github. Enjoy!

Update: Thanks to Tom Lokhorst, my talk is also on video.

2009-09-09

"Upwards and downwards accumulations on trees" translated into Haskell

I was reading "Upwards and downwards accumulations on trees" by Jeremy Gibbons, and it's written in the Bird-Meertens formalism (a.k.a. Squiggol) of yesteryear. Not that I have anything against people who can write and understand this stuff (in fact, I have a lot of respect for them), but for me, the inconsistent and seemingly arbitrary notation leaves something to be desired. In an attempt to understand what was actually being done, I translated most of the equations to Haskell code. If you plan on reading this paper, here's hoping I could jump-start your comprehension with this contribution.

The only real issue that I ran into while performing this translation is in the function s_fork_sl2. The second component of the catamorphism, ((⊙ ↟ ≪) ∘ ≪²), does not have the expected type (b, b) -> a -> (b, b) -> (b, b). After attempting to puzzle through how to unify the two, I eventually gave up and just came up with a function that seemed to do what I thought it should do, pairs g (x, _) _ (y, _) = (g x y, x) where g :: b -> b -> b is ⊙. But I'm not sure whether there's a bug in the definition in the paper or the one in my code. The code seems to work for a few tests. If you've already read this paper or you're at all interested in debugging Squiggol, I would be happy to learn how this works.