Datatype-generic programming in TypeScript

We will start our exploration by defining runtime representation of some primitive types as well as records, and extract the type definitions from them.

Defining the tokens for primitive types is straightforward enough:

export interface TypeToken<T> {}

const num: TypeToken<Number> = {};
const str: TypeToken<String> = {};

The API we're going to provide for records would be a function taking a record of type tokens and returning the type token for combined record in the same way. Defining it is a bit more tricky, and requires some type machinery to be used in resulting function's signature.

First, RemoveToken: its purpose is to remove TypeToken type constructor. Consider it to be a type function that takes TypeToken<T> and returns T:

type RemoveToken<T> = T extends TypeToken<infer Token> ? Token : never;

This definition uses a couple of neat features of TypeScript's type system: ability to define types conditionally, and to use infer keyword in front of a type variable, that, unsurprisingly, infers the "value" of the type variable, instead of requiring to provide it. Here, we just return the inferred type.

Now we need to do the same, but for the record type:

type RecordTokens<R> = {
    [k in keyof R]: RemoveToken<R[k]>
};

Now we use even more neat features: keyof operator, returning a union of literal strings of keys used in a record type, and ability to index the record type R with a type variable of type keyof R. Here is what this function does on an example:

With that out of the way, we're ready to define the function in all its glory:

function record<R extends Record<string, TypeToken<any>>>(r: R): TypeToken<RecordTokens<R>> {
    return {}
}

And here is how we can use it:

const cat = record({
    name: str,
    age: num,
});

type Cat = RemoveToken<typeof cat>;

As it stands, this code is not particularly useful. However, the cool thing is that using those tokens allows one to derive types from values using TypeScript's type inference.

Let's see what is possible to with this style of definitions when those "tokens" have some additional functionality. One thing is validation: see the runtypes library that uses the same approach.

I'm going to show a different thing and implement a generic traversal of types defined in this way. In order to do that, we have to add a method into token to process a value using a provided visitor. I'm going to use SAX-style visitor for simplicity:

export interface EventVisitor {
    number(num: number): void;
    string(s: string): void;
    startRecord(): void;
    startPair(key: string): void;
    endPair(): void;
    endRecord(): void;
}

With that in mind, the definitions of primitive and compound type tokens is straightforward:

interface TypeToken<T> {
    accept(value: T, visitor: EventVisitor): void
}

const num: TypeToken<number> = {
    accept: function (value: number, visitor: EventVisitor): void {
        visitor.number(value);
    }
};

const str: TypeToken<string> = {
    accept: function (value: string, visitor: EventVisitor): void {
        return visitor.string(value);
    }
};

function record<R extends Record<string, TypeToken<any>>>(r: R): TypeToken<RecordTokens<R>> {
    return {
        accept: function (value: RecordTokens<R>, visitor: EventVisitor): void {
            visitor.startRecord();
            for (const [k, v] of Object.entries(r)) {
                visitor.startPair(k);
                const child = value[k];
                v.accept(child, visitor);
                visitor.endPair();
            }
            visitor.endRecord();
        }
    }
}

Let's look at an example. Say, we want to transform an element of arbitrary type (built using our type tokens, of course) into an HTML list using this visitor. Here is a possible implementation:

class ListBuilder implements EventVisitor {
    chunks: string[] = [];
    number(num: number): void {
        this.chunks.push(num.toString());
    }
    string(s: string): void {
        this.chunks.push(s);
    }
    startRecord(): void {
        this.chunks.push("<ul>")
    }
    startPair(key: string): void {
        this.chunks.push(`<li>${key}: `)
    }
    endPair(): void {
        this.chunks.push("</li>")
    }
    endRecord(): void {
        this.chunks.push("</ul>")
    }
    build(): string {
        return this.chunks.join('');
    }
}

And here is how it's used:

const program = record({
    filename: str,
    purpose: str,
    version: num,
    language: record({
        name: str,
        version: str
    })
});

type Program = RemoveToken<typeof program>;

const thisProgram: Program = {
    filename: 'generic.ts',
    purpose: 'Demonstrate datatype-generic programming in TypeScript',
    version: 3,
    language: {
        name: 'TypeScript',
        version: '4.5.3'
    }
};

const visitor = new ListBuilder();
program.accept(thisProgram, visitor);
console.log(visitor.build());

And it indeed does generate valid HTML! Here's the pasted version: