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.

Advertisements
Parametric open recursion, Pt. 2

One thought on “Parametric open recursion, Pt. 2

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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