Extensible TypeScript with Object Algebras

A lightweight approach to maintainable systems

We say that code is “extensible” when it can be augmented with additional behavior without requiring modifications to existing code. Extensibility is a valuable property because it allows systems to grow over time without unnecessary rework. Under traditional idiomatic development most systems have undesirable limits on their extensibility: systems based on object-oriented programming (using autognostic objects) are extensible representationally, allowing us to easily add new kinds of data which conform to an existing interface, while systems based on functional programming (using algebraic data types) are extensible operationally, allowing us to easily add new functions which operate on existing data types. Under straighforward usage, both paradigms require us to choose one form of extensibility at the cost of the other. Techniques such as the visitor pattern can allow us to trade representational extensibility for operational extensibility but are not enough to achieve both kinds simultaneously.

This tension is referred to as “the expression problem”, a term coined by Philip Wadler in a 1998 email. A number of solutions to the expression problem have been discovered over the years but most rely on language and type system features which are not available in most mainstream programming languages. It wasn’t until 14 years later that a widely accessible solution to the problem was found and published. In the 2012 ECOOP paper “Extensibility for the masses: Practical extensibility with Object Algebras” Bruno Oliveira and William Cook described a pattern for solving the problem which worked in Java, requiring only object subtyping and generic interfaces. This blog post is about how this pattern can be used in TypeScript.

The paper’s description of the approach involves a non-negligible amount of boilerplate and the use of class-based inheritance due to the limited expressivity of the Java language. TypeScript developers are fortunate enough to be working with a significantly more flexible language which permits a very lightweight approach to the pattern. This post will show both approaches in turn.

In addition to the original paper on the topic, this post draws on the conference talk “Who’s Afraid of Object Algebras?” in which Tijs van der Storm demonstrates the pattern in the Dart programming language.

The expression problem #

To set the stage, here is the expression problem as Wadler originally stated it:

The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts). For the concrete example, we take expressions as the data type, begin with one case (constants) and one function (evaluators), then add one more construct (plus) and one more function (conversion to a string).

The testbed he proposes (which is used by the 2012 paper and by the rest of this blog post) is a calculator-like library, in which one may define, evaluate, and pretty-print arithmetic expressions.

To illustrate the challenge, here is a minimal implementation of the single-case single-function situation in object-oriented TypeScript:

interface Expr {
    evaluate: () => number;
}

class Constant implements Expr {
    private readonly value: number;

    public constructor(value: number) {
        this.value = value;
    }

    public evaluate(): number {
        return this.value;
    }
}

All this library can do is create Constant objects, which contain a value, and evaluate those constants, getting their value.

Because we are in object-oriented land we can easily add an additional case for Addition, as the problem statement requests:

class Addition implements Expr {
    private readonly left: Expr;
    private readonly right: Expr;

    public constructor (left: Expr, right: Expr) {
        this.left = left;
        this.right = right;
    }

    public evaluate(): number {
        return this.left.evaluate() + this.right.evaluate();
    }
}

With these two in place, we can now build up and evaluate mathematical expressions:

const four = new Addition(
    new Addition(new Constant(1), new Constant(1)),
    new Constant(2));

console.log(four.evaluate()); // prints "4"

The next request in the problem is to add a way to pretty-print our expressions, and this is where we’re snookered. To rephrase the Wadler email in object-oriented terms, we need to add a new method to the Expr interface: print: () => string;. But adding a member to an interface is a breaking change; once we do so our existing Constant and Addition classes will have to be modified. We are not extensible.

For completeness’s sake, here is what this sort of object-oriented solution would look like if we implemented it non-extensibly. Note that we have had to modify the Constant and Addition classes to add the new interface member.

interface Expr {
    evaluate: () => number;
    print: () => string;
}

class Constant implements Expr {
    private readonly value: number;

    public constructor(value: number) {
        this.value = value;
    }

    public evaluate(): number {
        return this.value;
    }

    public print(): string {
        return `${this.value}`;
    }
}

class Addition implements Expr {
    private readonly left: Expr;
    private readonly right: Expr;

    public constructor (left: Expr, right: Expr) {
        this.left = left;
        this.right = right;
    }

    public evaluate(): number {
        return this.left.evaluate() + this.right.evaluate();
    }

    public print(): string {
        return `${this.left.print()} + ${this.right.print()}`;
    }
}

A similar result will be obtained if you approach this problem using abstract data types (simulated through the use of brands, as shown in my previous post on the topic.) In that case you will easily be able to add the print function, but will be unable to add the Addition type to the Expr sum type without breaking existing conditional logic. I’ve omitted the full implementation here to save space.

A class-based implementation of object algebras #

To keep things close to the source material, I will start with a traditional-looking object oriented implementation of object algebras. The examples here will resemble the style of the Oliveira & Cook paper, as well as the van der Storm presentation.

Detour: algebraic signatures #

At this point it becomes necessary to explain why the term “algebras” is used. In the case of object algebras it refers to the algebraic signature of a data type. This is a method of mathematically describing data which has been used in the field of abstract algebra for decades. Under this approach, the definition of our expression type might look like this:

signature Expr
    constant: number -> Expr
    addition: (Expr, Expr) -> Expr

This is a description of the valid ways in which we can create an Expr, our expression type. We can either turn a number into an Expr using our constant constructor, or we can combine two Exprs into a new Expr using our addition constructor. Importantly, a signature does not specify either what an Expr is or how an Expr is created; it solely defines the dependencies needed to assemble one using each of the available constructors.

Translated into TypeScript, we can define these signatures using a generic interface:

interface ExprAlgebra<E> {
    constant: (value: number) => E;
    addition: (left: E, right: E) => E;
}

Here we have the same properties as before: ExprAlgebra<E> says that we can create an E using specific inputs, but does not specify what an E actually is. As an interface it also doesn’t say how an E is created, and instead leaves that up to whatever object implements the interface. We’ll take advantage of both of these forms of polymorphism when we assemble our extensible implementation.

Implementing the base case #

Let’s approach our previous example again, using object algebras to define our interfaces. This time the example will start with a minimal implementation and grow it incrementally through the extensible addition of new features.

The goal is to end up with expressions that are either constants or additions, and where we can both evaluate and stringify expressions. The first step is to define an interface for our evaluation operation:

interface Evaluatable {
    evaluate: () => number
}

The next step is to define an algebra for the construction of our data:

interface ConstantAlgebra<E> {
    constant: (value: number) => E;
}

As before, we start solely with constants and the ability to evaluate them.

We have interfaces but no implementation. Somewhere has to define what it looks like to evaluate a constant, and so we’ll make a class which holds that logic:

class EvaluatableConstant implements Evaluatable {
    private readonly value: number;

    public constructor(value: number) {
        this.value = value;
    }

    public evaluate(): number {
        return this.value
    }
}

Now that we have the logic for evaluating a constant as well as an algebraic interface for creating a constant we need a way to connect the two. We do so by making an implementation of our ConstantAlgebra interface which knows how to construct an EvaluatableConstant:

class EvaluatableConstantFactory implements ConstantAlgebra<Evaluatable> {
    public constant(value: number): EvaluatableConstant {
        return new EvaluatableConstant(value);
    }
}

The name “Factory” here comes from the classic Gang of Four book on object-oriented patterns. In pattern terms, our ConstantAlgebra interface is an “Abstract Factory” (with the twist that abstract factories in the Gang of Four book don’t usually take a generic argument.)¹

Now we have all four pieces of an object algebra implementation:

1. An interface describing the operations we want to perform

2. An abstract factory describing the algebraic signature of our data types

3. A concrete factory which implements the abstract factory interface, which knows how to construct concrete data

4. A concrete class which implements the operation for a given data type

With this implementation in hand we can finally use our algebra to create a constant and evaluate it to a value. Doing so requires assembling all of these moving pieces:

function makeThree<E>(factory: ConstantAlgebra<E>): E {
    return factory.constant(3);
}

const three = makeThree(new EvaluatableConstantFactory());
console.log(three.evaluate()); // prints 3

Whew. There’s a lot of indirection here, but as we’ll see in the next section this is not necessarily a bad thing. A couple of points should be noted:

• Constructing values is done inside of a wrapper function, which takes a factory as an argument.

• When we create values we do so by specifying up-front the way in which they will be used. The three we created using a factory isn’t some general constant for us to consume with arbitrary functions; it’s specifically a constant with an evaluate method. The function makeThree is general purpose, but the value it returns is specific.

Growing our class-based implementation with new constructors #

The ability to wrap and unwrap numbers in constants isn’t very impressive, so let’s take the slightly less unimpressive step of implementing basic addition. We will do so without breaking any existing code.

We’re reusing our existing evaluate operation from the Evaluatable interface, so we already have item #1 on our object algebra checklist done.

Item #2 is an abstract factory that can produce our data types. In this case we want to support the existing data type, constant, and a new data type, addition. We don’t want to duplicate the definition of constant, so we’ll make our new abstract factory extend our old one with a new field:

interface ExpressionAlgebra<E> extends ConstantAlgebra<E> {
    addition: (left: E, right: E) => E
}

Item #3 is a concrete factory that implements our abstract factory, and item #4 is a class which provides the actual logic which performs the operation on our data type. Here’s the two of them together:

class EvaluatableAddition implements Evaluatable {
    private readonly left: Evaluatable;
    private readonly right: Evaluatable;

    public constructor(left: Evaluatable, right: Evaluatable) {
        this.left = left;
	this.right = right;
    }

    public evaluate(): number {
        return this.left.evaluate() + this.right.evaluate();
    }
}

class EvaluatableExpressionFactory
    extends EvaluatableConstantFactory
    implements ExpressionAlgebra<Evaluatable> {

    public addition(left: Evaluatable, right: Evaluatable): Evaluatable {
        return new EvaluatableAddition(left, right);
    }
}

Note the use of inheritance in EvaluatableExpressionFactory to avoid having to duplicate the definition of constant from our existing code. This may leave a sour taste in some developer’s mouths but we’ll see how to avoid this in the TypeScript-y implementation later. In this case inheritance is not that bad; we don’t need to worry about the fragile base class problem because we’re writing extensible code in which base classes won’t generally need to be modified. That said, as the implementation grows some difficulties will arise regarding the lack of multiple inheritance in TypeScript. More on that later.

Now that we have our various pieces we can assemble them to evaluate expressions which contain both constants and addition:

function makeTwelve<E>(factory: ExpressionAlgebra<E>): E {
    const three = makeThree(factory);
    const twelve = factory.addition(
    	three,
        factory.addition(
            factory.constant(4),
            factory.constant(5)));
    return twelve;
}

const twelve = makeTwelve(new EvaluatableExpressionFactory());
console.log(twelve.evaluate()); // prints 12

We were able to reuse the function makeThree here. makeThree was defined on an algebra which only supported constants, but because ExpressionAlgebra is a subtype of ConstantAlgebra we could pass an ExpressionAlgebra factory into a function which expects a ConstantAlgebra. Put another way: we don’t lose the ability to call existing functions when we extend an algebra with new constructors. Our functions are forwards-compatible with unexpected additions to our domain model.

Adding new operations to a class-based implementation #

Being able to extensibly add new data variants is nice, but standard object oriented programming gives us that already. Where object algebras shine is the ability to also add new operations on our data; we’ll explore this now. We’re going to add support for the following operation:

interface Stringifiable {
    stringify: () => string
}

As before, we need to write classes which define what it means to apply this operation to each of our data variants:

class StringifiableConstant implements Stringifiable {
    private readonly value: number;

    constructor(value: number) {
        this.value = value;
    }

    public stringify(): string {
        return String(this.value);
    }
}

class StringifiableAddition implements Stringifiable {
    private readonly left: Stringifiable;
    private readonly right: Stringifiable;

    constructor(left: Stringifiable, right: Stringifiable) {
        this.left = left;
	this.right = right;
    }

    public stringify(): string {
        return `${this.left.stringify()} + ${this.right.stringify()}`;
    }
}

We don’t need to define a new abstract factory interface because we aren’t adding any new data variants. All that’s left is to define the concrete factory which constructs stringifiable objects:

class StringifiableExpressionFactory implements ExpressionAlgebra<Stringifiable> {
    public constant(value: number): Stringifiable {
        return new StringifiableConstant(value);
    }

    public addition(left: Stringifiable, right: Stringifiable): Stringifiable {
        return new StringifiableAddition(left, right);
    }
}

This gives us the ability to create and use stringifiable values:

function makeFour<E>(factory: ExpressionAlgebra<E>): E {
    return factory.addition(factory.constant(2), factory.constant(2));
}

const four = makeFour(new StringifiableExpressionFactory());
console.log(four.stringify()); // prints "2 + 2"

More importantly, this gives us the ability to re-interpret existing expression logic in a new way. Consider makeTwelve from before. We can now use it with our stringification logic without any modification to the original code:

const stringifiableTwelve = makeTwelve(new StringifiableExpressionFactory());
console.log(stringifiableTwelve.stringify()); // prints "3 + 4 + 5"

I don’t know about you, but I find this incredibly cool. Object algebras decouple the structure of data from its interpretation. We can write a function which creates a graph of objects and then define totally new logic which works on it, without giving up object-oriented goodness like extensible variants, encapsulation, and subtyping.

TypeScriptifying the pattern #

That concludes the introduction to class-based object algebras. To finish up, I’ll show an alternative encoding of them which takes better advantage of TypeScript’s flexibility.

Cutting boilerplate with higher-order functions #

A class with a single method is doing the job of a function, and indeed we can shed a great number of lines of code by using normal higher-order functions instead:

type Evaluatable = () => number;
type Stringifiable = () => string;

function evaluatableConstant(value: number): (() => number) {
    return () => value;
}

function evaluatableAddition(left: Evaluatable, right: Evaluatable): (() => number) {
    return () => left() + right();
}

function stringifiableConstant(value: number): (() => string) {
    return () => String(value);
}

function stringifiableAddition(
    left: Stringifiable,
    right: Stringifiable): (() => string) {

    return () => `${left()} + ${right()}`;
}

Cutting boilerplate by removing wrapper functions #

Another optional way to cut down on boilerplate is to remove the unnecessary wrapper functions shown above, and instead immediately interpret the value of each step. This means changing the return types of the functions, cutting out Evaluatable and Stringifiable entirely:

function evaluateConstant(value: number): number {
    return value;
}

function evaluateAddition(left: number, right: number): number {
    return left + right;
}

function stringifyConstant(value: number): string {
    return String(value);
}

function stringifyAddition(left: string, right: string): string {
    return `${left} + ${right}`;
}

This transformation is only sometimes desirable. For the purposes of evaluation and basic stringification it is adventageous, but consider a use-case like pretty-printing the abstract syntax tree for a more complicated language. When pretty-printing we may have to break code at the end of a line across lines based on how many characters there are at the start of that line. This means that we don’t know what the result of an inner value should be until we have computed its outer value. When each step returns an object we have the ability to compute something like this. If each step of evaluation just returned a string this would be unreasonably difficult; outer layers would have to re-parse the string they received in order to rebuild the abstract syntax tree’s lost structure.²

Cutting boilerplate by using anonymous objects #

The factory classes shown in the class-based section are also unnecessarily verbose. In TS we don’t need to make everything a class; we have first-class anonymous objects which can contain functions. Here’s an improved version of the class-based StringifiableExpressionFactory, which also uses the more lightweight direct-style interpretation from the last section:

const stringifiableExpressionFactory = {
    constant: (value: number) => stringifyConstant(value),
    addition: (left: string, right: string) => stringifyAddition(left, right)
}

The transformation from the class-based stringification factory to the anonymous-object-based one is straighforward, but this same transformation on the evaluation factory would not be. Recall that we used inheritance in the definition of the factory for evaluating expressions. I said at the time that this would run into problems with multiple inheritance; we’ll see how that plays out in the next section. Spoiler alert: TypeScript has a leg up on Java here, too.

Composing object algebras #

For the final step on this journey, let’s look at how object algebras can be combined and remixed as needed. In the class-based example we saw these things:

interface ExpressionAlgebra<E> extends ConstantAlgebra<E> { /* ... */ }

class EvaluatableExpressionFactory extends EvaluatableConstantFactory {
    /* ... */
}

This lets us bolt-on additional functionality to a single object algebra. It does not help us if we wish to combine multiple algebras. For instance, what if we already had two separate algebras for working with constants and addition, and we wanted to combine them into an algebra which could handle both?

The starting point might look something like this:

// One algebra for constants

type ConstantAlgebra2<E> = {
    constant: (value: number) => E;
}

const evaluateConstant2 = (value: number) => value;

const evaluatableConstantFactory = {
    constant: evaluateConstant2
}

// Separate algebra for addition

type AdditionAlgebra2<E> = {
    addition: (left: E, right: E) => E;
}

const evaluateAddition2 = (left: number, right: number) => left + right;

const evaluatableAdditionFactory = {
    addition: evaluateAddition2
}

We need to somehow merge ConstantAlgebra2 with AdditionAlgebra2, and we need to merge evaluatableConstantFactory with evaluatableAdditionFactory. The original ECOOP paper provides a way to combine multiple algebras using “object algebra combinators”. I’m omitting their implementation for Java-like classes; interested readers may check the paper. Fortunately the implementation needed in non-class-based TypeScript is incredibly minimal. There’s no “framework” code needed, only JavaScript’s built-in Object.assign and TypeScript’s built-in &. With these we can create a combined algebra for expressions by composing our previous two, with no inheritance in sight:

type ExpressionAlgebra2<E> = ConstantAlgebra2<E> & AdditionAlgebra2<E>;

const evaluatableExpressionFactory = Object.assign({},
    evaluatableConstantFactory,
    evaluatableAdditionFactory);

Putting it all together #

I’ve scattered implementation snippets all around this blog post. So for clarity, here’s our running example, TypeScript-style, all together in its final form:

// Algebraic signatures

type ConstantAlgebra<E> = {
    constant: (value: number) => E;
}

type AdditionAlgebra<E> = {
    addition: (left: E, right: E) => E;
}

type ExpressionAlgebra<E> = ConstantAlgebra<E> & AdditionAlgebra<E>;

// Evaluation logic

const evaluateConstant = (value: number) => value;
const evaluateAddition = (left: number, right: number) => left + right;

const evaluatableConstantFactory = {
    constant: evaluateConstant
}

const evaluatableAdditionFactory = {
    addition: evaluateAddition
}

const evaluatableExpressionFactory = compose(
    evaluatableConstantFactory,
    evaluatableAdditionFactory);

// Stringification logic

const stringifyConstant = (value: number) => String(value);
const stringifyAddition = (left: string, right: string) => `${left} + ${right}`;

const stringifiableExpressionFactory = {
    constant: stringifyConstant,
    addition: stringifyAddition
}

// Usage example

function makeFour<E>(factory: ExpressionAlgebra<E>): E {
    return factory.addition(
        factory.addition(factory.constant(1), factory.constant(1)),
	factory.constant(2));
}

console.log(makeFour(evaluatableExpressionFactory))   // prints "4"
console.log(makeFour(stringifiableExpressionFactory)) // prints "1 + 1 + 2"

Is this a lot of code to do addition? Yes. But compare it to the non-extensible object-oriented approach from the beginning of this post. In terms of non-whitespace lines of code they’re roughly the same length! Once you’re familiar with the pattern the code size of the object algebra approach is not unreasonable. Object algebras require some indirection but their carrying cost is not very high and their benefits can be huge.

Conclusion #

I think object algebras have the potential to be revolutionary in the way we build and extend software, were they to be adopted widely. If you’ve made it this far I deeply thank you for reading³. I hope that you’ve learned something useful, and I especially hope that these ideas might percolate into the way you write your own code.

Our industry by and large builds software which is closed off and disposable. End users cannot modify applications and libraries. Software systems tend to get progressively more gnarled as they are extended with additional functionality, assuming they are not thrown out and rewritten entirely. It would be better if more code could be extended, reused, remixed, both by its original authors and by third parties. Widespread use of object algebras could be a way to achieve that.

All code samples in this post are released into the public domain under a Creative Commons 0 license. Code samples and full license text may be found here.