Skip to content

Instantly share code, notes, and snippets.

@sampsyo
Last active August 9, 2023 23:54
Show Gist options
  • Save sampsyo/7f1fa4f2ebc10088a7d6 to your computer and use it in GitHub Desktop.
Save sampsyo/7f1fa4f2ebc10088a7d6 to your computer and use it in GitHub Desktop.
function inheritance in TypeScript
// 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));
.PHONY: run
run: fib.js
node $^
fib.js: fib.ts
tsc --noImplicitAny $^
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment