Parametric open recursion, Pt. 1

Consider the following situation: I need to define a function Param -> a -> b so that given a parameter p : Param my algorithm precomputes a function a -> b. Emphasis here goes to precomputation, which you can assume is an expensive operation. There are a few examples of such a pattern, this could be a regular expression parser (or indeed any parser), a denotational semantics, or, as it happens in my case of interest, a function that takes a type and returns a serializer for that type.

All this might sound a bit trivial, but what happens if I need to add recursion into the mix? What if I needed to define the Kleene star in terms of itself or if I needed to define serialization rules for (mutual) recursive types? One would be inclined to point out that this is easily solvable by applying the traditional fixpoint combinator, but this does not play well with our original assumption: the so-called precomputation stage will have to be performed every time a recursive call is made, which renders it neither efficient nor a precomputation.

Poly-variadic fix-point combinators

It is a well-known fact that mutual recursion can be encoded into the traditional Y combinator. This idea is reflected in certain constructs that allow the definition of mutual recursive functions without utilizing explicit language support for such. These are known as poly-variadic fixpoint combinators. An interesting example lies with Haskell, whose non-strict semantics permit a very succinct implementation:

How do you define the same combinator in a strict language like F#? There a few ways you could go about doing that, like wrapping around lazy types or fixing the arity of your defined functions, but it turns out you can preserve the original type signature with a bit of cheating:

This really works, and you can try it out for yourself at F# snippets. In fact, as my colleague Nick Palladinos has pointed out, it is significantly more efficient than your standard Y combinator (even though it remains orders of magnitude slower than idiomatic tail recursion).

A key observation to be made about this implementation is the use of “eta expansion” over the function references. The resulting functions have the property of preserving the content of the enclosed ref cell at the time of invocation. I would call this transformation “delayed dereferencing”, but I leave it to the more PLT inclined to suggest a better name for this. It could be further noted that similar combinators are possible in other domains that support this notion of delay, such as tuples of functions or even lazy types.

In my next entry I will be describing how the above ideas can be applied to solve the parametric recursion problem in F#.

Parametric open recursion, Pt. 1

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s