Function Inheritance is Fun and Easy

September 26, 2015

Function inheritance is a simple technique for adding extensibility to recursive functions. I’m in the midst of writing a compiler, which is just a giant pile of recursive tree traversals, so function inheritance is repeatedly saving my tender behind from jumbled confusion.

This post demonstrates function inheritance with some TypeScript examples. Here’s a Gist with the complete, executable code for everything.

The Problem

Say you have a recursive function. It could be type checker or an interpreter, but let’s say it’s everybody’s favorite recursive function: fib. Here’s an exponential-time fib in TypeScript:

function fib (num: number): number {
  if (num === 0) {
    return 0;
  } else if (num === 1) {
    return 1;
  } else {
    return fib(num - 1) + fib(num - 2);
  }
}

That’s a nice fib! But what if you need to extend it—for example, to log calls to the function for debugging, or to memoize answers for a linear-time version? You could sneak some extra code into the top of fib. But mixing this extra behavior together with the “core” Fibonacci computation has the ordinary drawbacks of tight coupling:

It would be better to write these additional behaviors separately from fib and some how smash them together.

Function Inheritance

I learned this technique from a 2006 tech report by Daniel Brown and William Cook from UT Austin and from Matt Might’s related blog post. Brown and Cook pitch the idea as bringing the notion of “inheritance” from Object-Oriented Land to Functional World.

The basic recipe has three steps: write your recursive functions as generators; write your additional behaviors as mixins; and tie everything together using a fixed-point combinator.

Generators

The first step is to change your algorithm to take a function parameter and use that for any recursive calls. You’ll recognize this recursion elimination from any discussion of the Y combinator and recursion in the lambda calculus:

// A "generator," which will only be useful after we get its fixed point later.
function gen_fib(fself: (_:number) => number): (_:number) => number {
  // From here on, this looks like an ordinary recursive Fibonacci, except
  // recursive calls go to the curried `fself` function parameter.
  return function (num: number): number {
    if (num === 0) {
      return 0;
    } else if (num === 1) {
      return 1;
    } else {
      return fself(num - 1) + fself(num - 2);
    }
  }
}

We’ve changed the recursive calls to fib to instead go to the curried fself function argument. That name, fself, is meant to call to mind the “self” or pointer in OO languages. It plays a similar role in making this function extensible.

The new gen_fib function’s type is no longer number -> number. Instead, it’s a generator in Brown and Cook’s parlance. In their Haskell, generator types are written a -> a. In TypeScript, we can write gen_fib’s type like this:

type Gen <T> = (_:T) => T;
let gen_fib : Gen< (_:number) => number >;

The TypeScript syntax for function types is a little weird, because parameter names are required but ignored, but you can read (_:A) => B as a -> b in Haskell or ML notation.

Mixins

Step two is to write your additional “mixin” behavior as a combinator. Here’s a trace combinator that prints a message on every invocation:

function trace <T extends Function> (fsuper: T): T {
  return <any> function (...args: any[]): any {
    console.log('called with arguments: ' + args);
    return fsuper(...args);
  }
}

That fsuper name, like fself, is supposed to remind you of the corresponding OO concept. Calling it invokes the original version of the function that trace extends.

This trace implementation is a little hacky because it supports an arbitrary number of function arguments via ES6 “spread” syntax. For a less trivial example that also has stronger types, see the memoization combinator, memo, in that there Gist.

Tying It Together

The final code is to mash up the core code with the mixins. To do this in TypeScript, we’ll need two handy functional tools: a fixed-point combinator and function composition. Throw them in your util.ts.

Here’s a simple fixed-point combinator that works with any number of function arguments:

function fix <T extends Function> (f : Gen<T>) : T {
  return <any> function (...args: any[]) {
    return (f(fix(f)))(...args);
  };
}

The function composition function is even simpler:

function compose <A, B, C> (g : (_:B) => C, f : (_:A) => B): (_:A) => C {
  return function (x : A): C {
    return g(f(x));
  }
}

With those two pieces, we can apply our combinators to build real, recursive functions:

// Here's an ordinary recursive Fibonacci without any mixins.
let fib = fix(gen_fib);

// And here's a traced version.
let fib_trace = fix(compose(trace, gen_fib));

Calling these like fib(8) or fib_trace(8) does what you want. If you’re still not convinced this actually works, clone this Gist and type make. Feel the power!

For Compilers

Since embracing function inheritance last week, I’ve already used it twice in my prototype compiler:

As an aside, TypeScript is surprisingly comfortable as a language for compiler hacking. Gradual typing helps you stay mostly within the bounds of a sane, ML-reminiscent, mostly-functional subset while still admitting the occasional necessary sin like that untyped fixed-point combinator above.