Bidirectionalization for Free!

Now reading the POPL'09 proceedings (36th Annual symposium on Principles of Programming Languages, Georgia, USA). So far, the most interesting paper is Bidirectionalization for Free!, by Janis Voigtländer. The author presents a Haskell function that, given a get function, yields a matching put function. But perhaps some explanations are in order.

A bidirectional transformation is a pair of functions, get and put. get accepts a data structure (such as a tree or an array) and returns a view of that structure: for example, the first n elements of an array, or the greatest element, or a flat view of a tree, etc. A matching put function accepts a data structure, and the result of a get; and modifies the data structure so that, if we apply get to it, the result will match.

Here are a few examples to explain what I mean. If the get function is take 2 (return the first two elements of an array), then put accepts an array a and and two elements t2, and returns a new array a' so that take 2 a' equals t2. So:

> get "hello"
"he"
> get "moose"
"mo"
> put "hello" "ye"
"yello"
> put "moose" "cl"
"close"

And here's a different example, where get is a function that removes duplicates from an array:

> get "database"
"datbse"
> put "database" "detbsi"
"detebesi"
> get "12341212345"
"12345"
> put "12341212345" "12*45"
"12*41212*45"

The hard part, of course, is defining put, given a get function. Each get has its own (very different) put. Previous approaches analyzed the source of get, and attempted to synthesize a matching put function. Voigtländer's solution is a function (called bff) that accepts get as a parameter, and produces a put function, without any access to the source -- just by analyzing how get acts on any given input. And it's not limited to arrays, either: it can work with much more complex data structures.

The author's explanations are lucid, and his solution is beautiful. You really do get bidirectionalization for (almost) free: the only price is performance, as bff's result is significantly slower than a hand-crafted put. But for rapid prototyping, or for work with small data sets, bff is more than enough. Another use (that the author fails to mention) is in unit-testing: if you do hand-craft a put for some get function, you can use bff to verify the correctness of your code.