Generics of a Higher Kind

Moors, Piessens and Odersky's paper Generics of a Higher Kind (OOPSLA 2008) describes a new feature in the Scala language, which is rapidly gaining popularity (the language, not the feature, that is).

This new feature, higher-level generics, allows for type parameters in more places, which reduces code duplication. For example, consider the definition of a trait (class component in Scala) called Iterable, and a sub-trait List which extends it. Iterable has a method, filter, which is abstract; and a method remove, which is implemented in terms of filter. Like this:

trait Iterable[T] {
  def filter(p: T => Boolean): Iterable[T]
  def remove(p: T => Boolean): Iterable[T] = filter (x => !p(x))
}

trait List[T] extends Iterable[T] {
  def filter(p: T => Boolean): List[T]
  override def remove(p: T => Boolean): List[T] = filter (x => !p(x))
}

Note how List has to repeat the declaration of both methods, just to specialize the return type. With higher-order generics, the code is made as simple as:

trait Iterable[T, Container[X]] {
  def filter(p: T => Boolean): Container[T]
  def remove(p: T => Boolean): Container[T] = filter (x => !p(x))
}

trait List[T] extends Iterable[T, List]

This might seem trivial, but try to do this in Java or C# generics to see why it isn't. This particular case was solved elsewhere with "current type" keywords (e.g., in Eiffel), but higher-order generics are more general than that and can be used in other cases, where the type parameter isn't the current type and (obviously) a current-type solution won't cut it.

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.

About This Blog

In this blog, I plan to post about interesting papers (and sometimes books) I've read, in the field of software engineering (and computing in general).

The choice of subjects will be completely eclectic, suited to my personal taste. But I hope it will be interesting enough to spur an occasional discussion.