Parametric open recursion, Pt. 2

In my previous post, I demonstrated how one can define poly-variadic fixpoint combinators in a strict language like F# using references. Today, we are going to expand on these ideas to construct a fixpoint combinator that allows open recursion over an indexed family of functions:

In this implementation, recursive bindings are made possible by early memoization of function references. This implies that an equality semantics is required for the domain of parameters. Also, just as in the poly-variadic case, the evaluation of references is delayed through the use of eta expansion.

Example: compiling regular expressions

Consider the following regular expression language:

Suppose I need to define a function Regex<'T> -> 'T [] -> bool which, given a regular expression, precomputes its recognizing predicate. There are many ways to write this, but the parametric combinator provides a particularly elegant solution:

Needless to say, the above will not work with the traditional Y combinator.

Extending the combinator

In the previous entry I described how the poly-variadic fixpoint can be extended beyond function spaces to any type that supports the notion of “delayed dereferencing”. The same pattern is observed with the parametric fixpoint. In fact, this construct can be generalized to a point where its type signature becomes essentially the same as that of the traditional Y combinator:

A similar version to the above can be found in the implementation of FsCoreSerializer.


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#.

Serializing F# types

One of the many performance challenges we have faced during our development of {m}brace is that of serialization. As you might have heard[1,2,3] {m}brace is a declarative cloud programming framework -currently under development- that aspires to become the “next big thing” in big data analytics.

Serialization performance of F types with the available .NET formatters is not exactly ideal, and this problem is amplified in our setting where transmission of arbitrary user-defined objects is commonplace. Some cases like trees are simply too slow, whereas others such as huge lists are outright fatal, leading to potential stack overflows.

Our solution to this problem is an implementation that at its core combines two ideas already out there:

  1. The excellent serializer by Anton Tayanovskyy ( that compositionally constructs its formatter functions by recursively traversing the reflected types of input objects.
  2. The FsReflect library by Kurt Schelfthout ( that uses dynamic methods to make the F# reflection API blazing fast.

The combination of the two yields a remarkably fast serializer when it comes to large tree structures and quotations. I have observed performance of up to 10-20x faster than BinaryFormatter or NetDataContractSerializer. Additionally, this implementation supports object caching, fallback serialization for non F# types, dynamic resolution of nested untyped fields and declaration of custom formatters. All round, this works as a general-purpose binary serializer.

I have named it quite unoriginally FsCoreSerializer and the source code has been uploaded to github. As always, your remarks and feedback would be very much appreciated.

EDIT: A nuget package is now available.