Our target data type is this:

  typedef adde = (
    `Int of int
    `Add of adde * adde
  );

Notice, it is a recursive data type. The function we want is

  fun evala (term: adde) =>
    match term with
    | `Int j => j
    | `Add (a,b) => evala a + evala b
    endmatch
  ;

Again notice it is a recursive function. We are going to recode our system using open recursion now. Here's the open version of the data type:

examples/openrecursion/openrec.flx

  typedef o_adde[T] = (
    | `Int of int
    | `Add of T * T
  );

Notice this data type is now polymorphic, but no longer recursive. The type variable has eliminated the recursion.

And here's the open version of the function:

examples/openrecursion/openrec.flx

  fun o_evala[T] (eval: T -> int) (term: o_adde[T]) =>
    match term with
    | `Int j => j
    | `Add (a,b) => eval a + eval b
    endmatch
  ;

Again, the function has become polymorphic, and has also acquired an extra parameter which is used to eliminate the recursive calls.

Now we are going to recover the original data type and function:

examples/openrecursion/openrec.flx

  typedef adde = o_adde[adde];
  fun evala (term:adde):int => o_evala[adde] evala term;

What we have done is close the open data type by replacing the type variable with a self-reference. Similarly, we have closed the function, by replacing the parameter with a self reference, so that the closed function now calls itself. Notice that in Felix, the return type of the recursion must be specified.

Here is a test case:

examples/openrecursion/openrec.flx

  var xa : adde = `Add (`Add (`Int 39, `Int 2), `Int 1);
  var yaa = evala xa;
  println$ "ya="+yaa.str; 

Now we're going to add a new feature: subtraction.

Here is the open version of the type and evaluator:

examples/openrecursion/openrec.flx

  typedef o_sube[T] = (
    | o_adde[T]
    | `Sub of T * T
  );
  fun o_evals[T] (eval: T -> int) (term: o_sube[T]):int =>
    match term with
    | `Sub (a,b) => eval a - eval b
    | o_adde[T] :>> k => o_evala eval k
    endmatch
  ;

Notice both the type and function delegate to the existing code for addition and only add support for our new operation, subtraction.

The closure of the the open type and function is called fixating them. What we have done is to manually introduce the self-reference. For the data type, we used a self-refering type alias; for the function we used eta-expansion.

It is possible to automate both these operations so they work on any suitably structured open types and functions using combinators called fixpoint operators.

Here's how we do it:

examples/openrecursion/openrec.flx

  typefun o_sube_f (T:TYPE) : TYPE => o_sube[T];
  typedef sube = tfix<TYPE> o_sube_f;
  fun evals (term:sube):int => (fix[sube,int] o_evals[sube]) term;

Here are the definitions from the standard library:

    fun fix[D,C] (f:(D->C)->D->C) (x:D) : C => f (fix f) x;
    typefun tfix<K> (f: K ->K):K => f x as x:K;

the type fixpoint cheats: it uses thefixpoint operator as which is builtin to the type system in the compiler.

The function fixpoint operator is interesting because its rather nasty type is what is required for an eager language. Lasy languages like Haskell have a simpler type for their function fixpoint operator.

Finally a test case:

examples/openrecursion/openrec.flx

  var xs : sube = `Add (`Sub (`Int 39, `Int 2), `Int 1);
  var yss = evals xs;
  var ysa = evals xa;  // ORGINAL DATA
  println$ "ys="+yss.str; 
  println$ "ya="+ysa.str; 

It's very important to notice that the original data also works with the new function! Of course it's obvious why: the function sube delegates to adde in that case.

Well .. actually it's not at all obvious when you think about it. What happens if you're adding two terms, one of which is a subtraction? How can the adde routine which appears to know nothing about subtraction do this?

The answer of course is we passed sube to it as a parameter! What's critical is this: the extenion is covariant and in particular the type adde is a subtype of sube.

Now we're going to make a second extension to the addition system to support multiplication. It follows a similar pattern to subtraction of course:

examples/openrecursion/openrec.flx

  typedef o_mule[T] = (
    | o_adde[T]
    | `Mul of T * T
  );
  fun o_evalm[T] (eval: T -> int) (term: o_mule[T]):int =>
    match term with
    | `Mul(a,b) => eval a * eval b
    | o_adde[T] :>> k => o_evala eval k
    endmatch
  ;
  typefun o_mule_f (T:TYPE) : TYPE => o_mule[T];
  typedef mule = tfix<TYPE> o_mule_f;
  fun evalm (term:mule):int => (fix[mule,int] o_evalm[mule]) term;
  var xm : mule = `Add (`Mul(`Int 39, `Int 2), `Int 1);
  var ymm = evalm xm;
  var yma = evalm xa;  // ORGINAL DATA
  println$ "ym="+ymm.str; 
  println$ "ya="+yma.str; 

We're no going to mix it all together and also add division.

examples/openrecursion/openrec.flx

  typedef o_dive[T] = (
    | o_sube[T]
    | o_mule[T]
    | `Div of T * T
  );
  fun o_evald[T] (eval: T -> int) (term: o_dive[T]):int =>
    match term with
    | `Div(a,b) => eval a / eval b
    | o_sube[T] :>> k => o_evals eval k
    | o_mule[T] :>> k => o_evalm eval k
    endmatch
  ;
  typefun o_dive_f (T:TYPE) : TYPE => o_dive[T];
  typedef dive = tfix<TYPE> o_dive_f;
  fun evald (term:dive):int => (fix[dive,int] o_evald[dive]) term;
  var xd : dive = 
    `Add (
      `Mul (
        `Int 39, 
        `Sub (
          `Int 3, 
          `Div (`Int 2, `Int 2)
        )
      )
      , 
      `Int 66 
    )
  ;
  var ydd = evald xd;
  var yda = evald xa;  // ORGINAL DATA
  var yds = evald xs;  // ORGINAL DATA
  var ydm = evald xm;  // ORGINAL DATA
  println$ "yd="+ydd.str; 
  println$ "ya="+yda.str; 
  println$ "ys="+yds.str; 
  println$ "ym="+ydm.str; 

Polymorphic variants (as in Felix or Ocaml) are essential for open recursion to work. However as is the case with all structural types with user supplied componenmts, including records, compiler error diagnostics are very hard to understand due at least in part the fact that all the components must be listed to identify the type. By contrast, nominal types are easy to refer to, since they have a single unique and simple name.

Ocaml has made significant progress in this area by the diagnostics ability to search the symbol to table to see if a compnent set happens to have a named alias.

In our simple example, the open version of a type has a single type variable, and the open version of a function has a functional parameter: the type variable and the paramater are eliminated by self-reference by using the fixpoint operators.

However in complex systems such as a compiler, we usually have main types, and auxilliay types they depend on; sometimes, we have two of more major types which are convoluted and inseparable: in these cases two or more type variables and function parameters may be required

This leads to a very difficult combinatorial explosion because now we can fixate one type variable whilst leaving the other open. Multiple extensions of one type can be used with multiple extensions of another.

In Felix, the type system terms in the compiler have at least 6 auxilliary types for which multiple flat extensions cold be provided leading to an unmanagably large potential set of closed terms. of course this is not a problem with open recursion at all: it is a simple fact, and a blessing that open recursion provides the machine to represent these choices. The existence of fixpoint combinators are then crucial because fixation closures are anonymous and can be provided as required "on the fly".

Nevertheless, using this technology in complex applications whilst the very environment where the modularity provided is of most benefit, is also the environment where it is hardest to get right. In the Felix compiler I found it so difficult, dynamic typing was prefered; that is, handling terms that should have been erased by throwing an exception was a lot easier than constructing a type for every use case so as to obtain a compile time error.

I think it remains to develop language constructions that can leverage this technology in a more manageable way.