function inheritance in TypeScript

fib.ts

// This is a quick demonstration of "function inheritance" as described in
// this paper from Daniel Brown and William Cook.
// http://www.cs.utexas.edu/users/wcook/Drafts/2009/sblp09-memo-mixins.pdf
// Expressed in TypeScript (and without the monads).

// Syntax note: When you write function types in TypeScript, you need to name
// each parameter. But the names don't actually matter, so I just use _. You
// can read `(_:A) => B` as `a -> b` in ML or Haskell syntax.

// In Brown and Cook's Haskell, `type Gen a = a -> a` is a "generator." The
// extensible functions we write will be "function generators."
type Gen <T> = (_:T) => T;

// We write the Fibonacci function as a generator. This is a curried function
// where the first parameter will be used to take a fixed point.
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.
  return function (num : number): number {
    if (num === 0) {
      return 0;
    } else if (num === 1) {
      return 1;
    } else {
      return fself(num - 1) + fself(num - 2);
    }
  }
}

// The `trace` mixin just logs the parameter every time the function is
// called.
function trace <T extends Function> (fsuper: T): T {
  // I want to make this work with any number of JavaScript function
  // arguments, but I think that means this has to be type-unsafe. For a
  // type-safe single-argument version, use:
  //
  // function trace <P, R> (fsuper: (_:P) => R): (_:P) => R {
  //   return function (p : P): R { ... };
  // }

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

// A memoization mixin. It's thunked to encapsulate a mutable memo table, so
// use it as `memo()` instead of just `memo`.
function memo <P, R> (): Gen<(_:P) => R> {
  // The memo table is a JavaScript object (not an ES6 Map, which is what we
  // really want), so only some parameter types will actually memoize
  // correctly.
  let cache : { [key: string]: any } = {};

  return function (fsuper: (_:P) => R): (_:P) => R {
    return function (p : P): R {
      // Cached.
      let r = cache[<any> p];
      if (r !== undefined) {
        return r;
      }

      // Uncached.
      r = fsuper(p);
      cache[<any> p] = r;
      return r;
    }
  }
}

// A fixed-point combinator.
//
// It supports any number of (uncurried) arguments. I don't think it's
// possible to typecheck this TypeScript, because you can't parameterize
// arbitrarily long lists of argument types. Hence all the `any`s.
function fix <T extends Function> (f : Gen<T>) : T {
  return <any> function (...args: any[]) {
    return (f(fix(f)))(...args);
  };
}

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

// Now, we can use `compose` with our mixins, `trace` and `memo`, to get
// different variants of our Fibonacci function! When we're done composing,
// use `fix` to tie the knot and get a useful function.

// For example, here's an ordinary recursive Fibonacci without any mixins:
let fib = fix(gen_fib);

// Here are memoized and traced versions:
let fib_trace = fix(compose(trace, gen_fib));
let fib_memo = fix(compose(memo(), gen_fib));

// And finally, here's a memoized *and* traced Fibonacci:
let fib_trace_memo = fix(compose(memo(), compose(trace, gen_fib)));

// Let's make sure this works.
console.log('ordinary fib:');
console.log(fib(4));
console.log(fib(7));
console.log(fib(8));

// This time, we should see evidence of the memoization in the traces: we
// should never see a repeated trace log for the same parameter.
console.log('\ntraced and memoized:');
console.log(fib_trace_memo(4));
console.log(fib_trace_memo(7));
console.log(fib_trace_memo(8));

// Here's a contrived example of a function with multiple parameters.
function gen_contrived(fself: (a: number, b: number) => number) {
  return function(a: number, b: number): number {
    if (a == 1 || b == 1) {
      return 1;
    } else {
      return fself(a - 1, b) + fself(a, b - 1) + 2;
    }
  };
}
let contrived = fix(gen_contrived);
let contrived_trace = fix(compose(trace, gen_contrived));
console.log('\na multi-argument recursive function:');
console.log(contrived(2, 3));
console.log(contrived(3, 4));
console.log(contrived_trace(2, 3));
console.log(contrived_trace(3, 4));

makefile

.PHONY: run
run: fib.js
	node $^

fib.js: fib.ts
	tsc --noImplicitAny $^