Department of Computer Science
Cornell University

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

• Your logging or memoization code isn’t reusable; it’s tied to `fib`.
• You can’t easily get the original non-logged, non-memoized variant of `fib` if you need it too.
• In more complicated recursive functions than `fib`, where there are lots of cases, this can lead to overwhelming boilerplate and can obscure the original computation.

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:

• Type elaboration. Instead of mucking up my type checker with AST-manipulation boilerplate, I use something like memoization to save its results in a symbol table. Thanks to Preston Briggs for this idea.
• Desugaring. I wrote a pure-boilerplate generator, called `gen_translate`, that just copies an AST without changing it. Then I wrote a mixin to encapsulate pattern matching and replacement for some specific syntactic sugar. Mashed together, the resulting function copies most of the tree unchanged while desugaring parts of it. It will be straightforward to add new desugaring rules in the future.

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.