Destroy All Dependencies, or: why structural typing is awesome
Tags: typescript, javascript, oop, codequality
Published: 2020-12-02 10:19:43

---
title: Destroy All Dependencies, or: why structural typing is awesome
published: true
canonical_url: https://listed.to/@crabmusket/20296/destroy-all-dependencies-or-why-structural-typing-is-awesome
description: A journey towards a single-responsibility module in TypeScript.
tags: typescript, javascript, oop, codequality
//cover_image: https://direct_url_to_image.jpg
---

When designing software, we strive to ensure each module, class, or function has a _single responsibility_. We want to be able to reuse small, focused pieces of code, and we want our tests to be clean and understandable.

But a piece of software as a whole usually has more than one responsibility! Sindre Sorhus, noted developer of small NPM modules, puts it succinctly [in this comment][1]:

> You make small focused modules for reusability and to make it possible to build larger more advanced things that are easier to reason about.

Our modules should be small and focused, but the end goal is to _integrate_ them into a larger whole. This means the modules that make up our applications must have _dependencies_ between each other; they cannot live in blissful isolation.

This means that **dependencies are a necessary evil in software development.**

Because dependencies are a **necessary evil**, we try to keep control of them as much as possible. According to Sandi Metz [in her excellent book][2]:

> Object-oriented design is about managing dependencies. It is a set of coding techniques that arrange dependencies such that objects can tolerate change ... In the absence of design, unmanaged dependencies wreak havoc because objects know too much about one another.

While Sandi is talking about _object-oriented_ design in particular, the principle applies to all ways of designing programs. Carefully managing the dependencies of each module of code you write will lead to cleaner, less-tightly-coupled code that's easier to test and reuse.

The example in this article will use TypeScript in object-oriented style. We're going to look at a piece of code with some obvious   dependencies and some subtle ones, and then we'll use a few well-known techniques to remove as many of those dependencies as we can. The concepts and tools we'll use are:

- The single-responsibility principle
- The dependency injection pattern
- Duck typing
- TypeScript's structural typing capabilities
- Generics and the principle of parametricity

After our changes, we'll have made our module much more reusable and more robust to changes in the rest of the application it's part of.

_If you want the TLDR, you can skip to [the starting code](#breadthfirst-search-with-lots-of-dependencies) and [the final result](#recapping-our-journey)_

### A note about static types

Part of the inspiration for writing this article was the idea that dynamically-typed languages have it easier than statically-typed languages when it comes to reusability. Because types don't have to be declared, imported, and pinned down, the code is unencumbered to do what needs to be done now, and to change in the future.

Type systems have come a long way in the last decade. New statically-typed languages have emerged and gone mainstream. Existing languages have gained new features.

In this post we'll end up writing code that feels very dynamic, even though it's statically-typed and safe. This is, I think, a real gift of TypeScript's type system, as you'll see.

### A disclaimer about premature design

Before we dive into the code, I want to point out that it's possible to do _too much design_ up-front. [Premature abstraction][11], [code that is too DRY][12], and imagining future requirements can all create more problems than they're worth.

But, that said, it's possible to write code that maintains more flexibility than less, even when all requirements aren't yet known. Different ways of coding the same behaviour can create fewer or more dependencies, without changing the level of DRYness or abstraction.

The advice in this post has two purposes:

1. To introduce you to some techniques which result in fewer dependencies, which you can apply _habitually_ when writing new code.
2. To help you learn how to apply these techniques when changing requirements _force_ you to break apart dependencies.

With that in mind, let's get started.

[11]: https://sandimetz.com/blog/2016/1/20/the-wrong-abstraction

[12]: https://www.justinweiss.com/articles/i-dry-ed-up-my-code-and-now-its-hard-to-work-with-what-happened/

## Breadth-first search with lots of dependencies

Take a look at this (incomplete) snippet of TypeScript code which implements [breadth-first search on a graph][3]:

```typescript
import {Graph} from "./graph";

export function breadthFirstSearch(
  nodes: Array<string>,
  edges: Array<[string, string]>,
  startingNode: string,
  nodeToFind: string
): Array<string> {
  let graph = new Graph(nodes, edges);

  let result: Array<string> = [];
  let visited: Array<string> = [];
  let queue: Array<string> = [startingNode];

  while (queue.length) {
    let node = queue.pop();
    let nodesToVisit = graph.successors(node);

    // algorithm omitted for brevity
  }

  return result;
}
```

I've omitted the meat of the BFS algorithm, but you can see the important parts, which are:

- Creating a `Graph` from the nodes and edges we're given
- Calling the graph's `successor` method, which returns the names of the nodes connected to the given node

The first thing we should do when looking at this code is ask ourselves: what dependencies does this code have? Have a think before reading on.

There's one obvious dependency: importing the `graph.ts` module at the top of the file. However, there are many implicit dependencies in this code, which take a little bit of thought to discern:

- What data to pass to the `Graph` constructor (nodes and edges)
- Where to find the `Graph` constructor (in `graph.ts`)
- What type of nodes the graph stores (each node is a `string`)
- The names of particular methods the `Graph` class has (in this case, just `successors`)
- How to call those `Graph` methods (e.g. `successors` takes a single `string` and returns an array of them)

You might not be used to thinking of things like class names and method parameter lists as dependencies. But they represent _knowledge about external code_, just as much as a hardcoded file location does. These pieces of knowledge tie our code to that external code, and mean that if the external code changes, our code will have to change too.

Some of these are necessary dependencies, but others are _incidental_. Incidental dependencies can be caused by careless design, but can be remedied just as easily. Let's take the first step in reducing our code's dependency on the outside world: reducing the amount of _responsibility_ it has.

## The single-responsibility principle

The [single responsibility principle](https://en.wikipedia.org/wiki/Single-responsibility_principle), which is a staple of object-oriented programming but can be applied anywhere, encourages us to write code so that _"a class should have only one reason to change."_

What is the _responsibility_ of our BFS function as it is currently written? If we were to describe it in one sentence, we might say it like this:

> breadthFirstSearch creates a Graph from the given nodes and edges, and searches for a path between two nodes within it.

The presence of an _and_ in that sentence indicates there is more than one responsibility. We need to find a way to remove the first responsibility. We'll find that in removing a responsibility, we also remove dependencies.

You might think that creating a `Graph` object is a mere implementation detail, of the same level of significance as creating the `result` array, for example. And you may certainly be right to think that! When looking at a snippet of code like this, outside the context of a wider application, it's hard to say. In every instance, you will need to think through what counts as a responsibility, what is a mere implementation detail, and where to draw the boundaries of your modules. My purpose here is to illustrate what _may_ be, not to proscribe the optimal way to structure breadth-first search algorithms.

Let's use the [dependency injection](https://en.wikipedia.org/wiki/Dependency_injection) pattern to remove the responsibility for creating a graph. To do that, we'll change the code as follows:

```typescript
import {Graph} from "./graph";

export function breadthFirstSearch(
  graph: Graph,
  startingNode: string,
  nodeToFind: string
): Array<string> {
  let result: Array<string> = [];
  // the rest remains unchanged
}
```

We removed the `nodes` and `edges` arguments, instead accepting a `graph` of type `Graph`. Instead of creating a dependent object, the function now accepts it as an argument. By doing that, it has refused to take responsibility for _creating_ the graph, even though it still depends on a graph existing at some point.

Let's look back at our list of dependencies and see how it's different now:

- ~~What data to pass to the `Graph` constructor~~
- **That `graph` is an instance of the `Graph` class**
- Where to find the `Graph` constructor
- What type of nodes the graph stores (each node is a `string`)
- The names of particular methods the `Graph` class has (in this case, just `successors`)
- How to call those `Graph` methods (e.g. `successors` takes a single `string`)

We seem to have introduced a new dependency, in the process of trying to remove one: now our code knows that the `graph` parameter is an instance of a class - the `Graph` class in particular.

This is a much smaller dependency. We've traded a large piece of knowledge - how to use the `Graph` constructor - for a smaller piece: merely that the `Graph` constructor exists.

But we would still like to remove this dependency entirely, rather than only shrinking it, if we can. And it turns out: we can.

## Duck typing with interfaces

Let's think for a moment about this new dependency we've introduced. It may be smaller than the original dependency, but it still has some troubling implications.

In a statically-typed language, declaring that `graph` has type `Graph` (where `Graph` is a class constructor) means that we can never pass anything into this parameter which is not an instance of the `Graph` class or one of its subclasses.

This might seem reasonable, but it does reduce the flexibility of our code. Object-oriented inheritance can be useful, but we shouldn't force it on users of our code without good reason to. Languages like C++ have typically used inheritance heavily to enable polymorphism, because they do not have alternatives. But in TypeScript, as in many modern object-oriented languages, we can do better.

We can apply a principle known as [duck typing][4] to remove the implicit dependency on the class hierarchy here. Instead of depending on a _specific class constructor_, we'll depend on an _interface_. The difference is that interfaces are not tied to any specific class hierarchy.

> In duck typing, an object's suitability is determined by the presence of certain methods and properties, rather than the type of the object itself.

Let's create a new file called `graph_interface.ts` to help with this. We'll declare all the capabilities of graphs which our application needs in one location:

`graph_interface.ts`:
```typescript
export interface GraphInterface {
  successors(node: string): Array<string>;
  predecessors(node: string): Array<string>;
  nodes(): Array<string>;
  edges(): Array<[string, string]>;
  // ... other graph methods
}
```

And we'll modify our BFS module like so:

```typescript
import {GraphInterface} from "./graph_interface";

export function breadthFirstSearch(
  graph: GraphInterface,
  startingNode: string,
  nodeToFind: string
): Array<string> {
  // the rest remains unchanged
}
```

Now, instead of depending on the `Graph` class itself, we depend on the new interface. Any type can implement this interface, regardless of a class's lineage. For example, we might end up creating new graph types that look like some of these:

```typescript
// This class of graph has no parent class
class SparseGraph implements GraphInterface {
  // ...
}

// This class is the child of a class from the JavaScript standard library
class AdjacencyMatrix extends Uint8Array implements GraphInterface {
  // ...
}

// This class is a child of our original Graph class
class DirectedGraph extends Graph implements GraphInterface {
  // ...
}
```

We have strictly increased the reusability of our code, because any type can stick to the interface our code needs. This is an example of the [duck typing][4] pattern:

Let's do another check of our dependency list:

- ~~That `graph` is an instance of the `Graph` class~~
- **That `graph` conforms to the `GraphInterface` type**
- Where to find the `GraphInterface` type
- What type of nodes the graph stores (each node is a `string`)
- The names of particular methods the `GraphInterface` type has (in this case, just `successors`)
- How to call those `GraphInterface` methods (e.g. `successors` takes a single `string`)

We've removed the `Graph` class dependency for good, and have modified the following dependencies to refer now to `GraphInterface` instead of `Graph`, but we've again introduced a new one dependency! (Will this nightmare ever end? Are we making progress, or just painting over the cracks in our shoddy design?)

As with the previous change we made, we've swapped a larger piece of knowledge for a smaller piece. The `Graph` class implied an inheritance hierarchy, but the `GraphInterface` does not. While numerically our dependencies have stayed the same, we've reduced the amount of knowledge they contain. This makes them more manageable.

But now, thanks to an important feature of TypeScript's type system, and the changes we've made up to this point, we can make a dramatic improvement.

## Duck typing _with structural types_

Astute readers will have noticed that in the last section, I gave some examples of classes that looked like this:

``` typescript
class DirectedGraph extends Graph implements GraphInterface {
  // ...
}
```

But in TypeScript, unlike most statically-typed languages, it's not necessary to declare `implements GraphInterface`. As long as a class is compatible with an interface _at the point of use_, TypeScript will be happy! We don't need to declare compatibility ahead of time.

This is known as _structural typing_. It's an extremely useful feature which we will now make use of. Structural typing contrasts to _nominative typing_, where the specific identity of each type is unique and significant. [Read more about structural and nominative typing.](http://wiki.c2.com/?NominativeAndStructuralTyping)

Because of structural typing, we don't have to depend on a shared interface defined elsewhere. Let's move the interface declaration right into our module, like this:

```typescript
interface GraphInterface {
  successors(node: string): Array<string>;
  predecessors(node: string): Array<string>;
  nodes(): Array<string>;
  edges(): Array<[string, string]>;
  // ... other graph methods
}

export function breadthFirstSearch(
  graph: GraphInterface,
  startingNode: string,
  nodeToFind: string
): Array<string> {
  // ...

  while (...) {
    let nodesToVisit = graph.successors(node);
    // ...
  }

  // ...
}
```

Now we don't import `GraphInterface`, but declare it _where it's needed_. This is an important ability in languages like TypeScript and Go.

Here, we can cross a dependency off our list and, thankfully, not introduce any new ones:

- That `graph` conforms to the `GraphInterface` type
- ~~Where to find the `GraphInterface` type~~
- What type of nodes the graph stores (each node is a `string`)
- The names of particular methods the `GraphInterface` type has (in this case, just `successors`)
- How to call those `GraphInterface` methods (e.g. `successors` takes a single `string`)

We no longer depend on the interface being found anywhere except _right here_ where it's used. We could rename every other file in our application, and this module would not even notice.

This is another big step forwards, but you might be getting a niggling feeling that something is wrong when looking at the code above. Let's take a moment to address that niggle.

## Increasing flexibility using the interface segregation principle

The niggle is probably coming from the fact that our newly-moved `GraphInterface` declares a bunch of methods that `breadthFirstSearch` _doesn't use_. For example, `predecessors` is never used.

This is a violation of the [interface segregation principle][5], which suggests that _"no client should be forced to depend on methods it does not use."_

This phrasing (from the Wikipedia page) is not a precise fit for our code example, but the principle definitely applies. Fortunately, we can easily remedy this, and in doing so increase the flexibility of our module.

Let's revise the `GraphInterface` like so:

```typescript
interface GraphInterface {
  successors(node: string): Array<string>;
}

export function breadthFirstSearch(
  graph: GraphInterface,
  startingNode: string,
  nodeToFind: string
): Array<string> {
  // ...

  while (...) {
    let nodesToVisit = graph.successors(node);
    // ...
  }

  // ...
}
```

Now that the interface has shrunk to include _precisely_ the functionality we need from it, it doesn't represent the entire concept of "graphness" any more, and we should probably rename it. (Luckily, this is safe to do, because the interface is not exported, so no external code could be depending on it!)

```typescript
interface BreadthFirstSearchable {
  successors(node: string): Array<string>;
}

export function breadthFirstSearch(
  graph: BreadthFirstSearchable,
  // ...
}
```

The interface is now acting as a declaration of the types of things that can be searched with our `breadthFirstSearch` function. For more exploration of this pattern, have a read of [this great blog post][6] which uses examples in Go, another structurally-typed language.

Let's take another look at our list of dependencies:

- ~~That `graph` conforms to the `BreadthFirstSearchable` type~~
- What type of nodes the graph stores (each node is a `string`)
- The names of particular methods the `graph` object has (in this case, just `successors`)
- How to call those methods (e.g. `successors` takes a single `string`)

I have modified the final two dependencies slightly, and in doing so, have made the first dependency redundant. Because our `BreadthFirstSearchable` interface perfectly fits just the methods our code actually uses, the interface itself is insignificant; it's merely a convenient syntax to declare how we will use the `graph` object.

## Take a breather

We've done extremely well so far, reducing our list of five weighty dependencies to three. Take a second to congratulate yourself!

If we stopped here, we could be proud of our work. We've successfully

- excised a responsibility that our module shouldn't have had in the first place,
- removed an import of an external file,
- abolished the implicit dependency on a class hierarchy

and in doing so, have made the code clearer and more focused. A side-effect of declaring interfaces _at the point of use_ is to have explicit documentation about what our breadth-first search module really _needs_ in order to work.

Notice that the remaining dependencies seem much more difficult to consider removing. After all, how could we make a BFS algorithm that doesn't depend on knowing the name of the `successors` method? Could we take this too far?

Of the dependencies that remain, I would argue the final two are very reasonable dependencies to keep. They express the core meaning of the code. Breadth-first search depends on searching the _successors_ of nodes in a graph. Each node may have zero, one, or many successors. These are fundamental facts about graph theory that we can't really get around. So it's unlikely we'll be able to remove these dependencies, no matter how clever we are.

However, the dependency on the `string` type can be dispensed of. If you want to try the Full Monty, read on to find out how.

## Using generics to reduce knowledge

Our code currently knows that each node in the `graph` is a `string`. This looks like a single piece of knowledge. But, like the `Graph` class implies an inheritance hierarchy, the `string` type implies other knowledge:

- Nodes can be compared using not just `==` and `===`, but `<`, `>`, `localeCompare`, etc.
- We can ask each node for its `.length`
- We can call `node.substring`
- Etcetera...

Built-in types like `string` usually bring a lot of knowledge with them, because they are designed to be feature-ful! Usually it's not a problem to rely on this knowledge. Built-in types change so infrequently (especially not in breaking ways) that it's very safe to leave these dependencies in your code.

However, knowledge of concrete types can sometimes reduce flexibility and reusability. An immediate example that comes to mind is that some graphs might have numeric identifiers instead of string-based identifiers.

Bearing in mind my advice at the beginning about not doing too much _premature design_ and not _anticipating requirements_, let's explore the way we can use generic types to make this code more flexible _if appropriate_.

First, let's make an alias of the `string` type, for clarity:

```typescript
type Node = string;

interface BreadthFirstSearchable {
  successors(node: Node): Array<Node>;
}

export function breadthFirstSearch(
  graph: BreadthFirstSearchable,
  startingNode: Node,
  nodeToFind: Node
): Array<Node> {
  let result: Array<Node> = [];
  let visited: Array<Node> = [];
  let queue: Array<Node> = [startingNode];

  while (queue.length) {
    let node = queue.pop();
    let nodesToVisit = graph.successors(node);
    // ...
  }

  return result;
}
```

It's now easier to see where we must insert type parameters in order to remove the knowledge of the specific type. After removing the alias `type Node` and adding generic parameters, the code looks like this:

```typescript
interface BreadthFirstSearchable<Node> {
  successors(node: Node): Array<Node>;
}

export function breadthFirstSearch<Node>(
  graph: BreadthFirstSearchable<Node>,
  startingNode: Node,
  nodeToFind: Node
): Array<Node> {
  // ...
}
```

We've successfully crossed off a piece of knowledge, and have made our code more flexible in the process. This is what our knowledge list looks like now:

- ~~What type of nodes the graph stores (each node is a `string`)~~
- The names of particular methods the `graph` object has (in this case, just `successors`)
- How to call those methods (e.g. `successors` takes a single `Node`)

## Parametricity is a cloud of unknowing

There's an esoteric concept known as _parametricity_ which is typically talked about in functional programming. This [article from Cambridge (PDF)][6] puts it thus (with added emphasis):

> Parametricity can be thought of as the dual to abstraction. Where abstraction hides details about an implementation from the outside world, parametricity **hides details about the outside world** from an implementation.

The use of a type parameter means our function _knows less_ about the outside world, which is what we wanted. This has interesting implications.

Our code now can't use methods of the String class like `substring`, because `Node` could mean any type, depending on the caller of our code.

As described handily in [this article][7] using Scala for examples, this lack of knowledge limits the choices we can make when implementing code. We can no longer accidentally use `node.length` or any other specific methods or properties. We are prevented from peering beyond the _cloud of unknowing_ created by the generic type parameter.

(Of course, because JavaScript has reflection, we can determine information about values with unknown types at runtime. However, `typeof` and `instanceof` are more likely to be asked about in code review than an innocuous `node.length`.)

But, significantly, the caller now also knows that our code is operating inside this _cloud of unknowing_. The caller knows that our code _cannot_ rely on `Node` being any specific type. This gives the caller more freedom and flexibility.

## Recapping our journey

Here's the code we've ended up with:

```typescript
interface BreadthFirstSearchable<Node> {
  successors(node: Node): Array<Node>;
}

export function breadthFirstSearch<Node>(
  graph: BreadthFirstSearchable<Node>,
  startingNode: Node,
  nodeToFind: Node
): Array<Node> {
  let result: Array<Node> = [];
  let visited: Array<Node> = [];
  let queue: Array<Node> = [startingNode];

  while (queue.length) {
    let node = queue.pop();
    let nodesToVisit = graph.successors(node);
    // the rest of the algorithm
  }

  return result;
}
```

And here is our list of knowledge that this code has about external code:

- The names of particular methods the `graph` object has (in this case, just `successors`)
- How to call those methods (e.g. `successors` takes a single `Node`)

We've come a long way, and reduced our knowledge to the very minimum. The remaining dependencies reflect the _core abstractions_ of our domain. This module should last unchanged for a long time, serenely weathering changes in the code surrounding it, without demanding to be changed in lockstep.

While it might seem like we might have looked into the future to imagine requirements this code might be fulfilling (e.g. new graph classes, or graphs with numeric nodes), the changes we've made were low-impact and broadly applicable to many situations. We didn't add new features, or introduce new abstractions: we systematically _removed knowledge_ from the code, and in doing so made it less dependent on the code around it, and more reusable in unexpected future contexts.

I hope that next time you're writing new code, or refactoring a tangled web of dependencies, these techniques and ways of understanding dependency will help you cut through the chaos and discover clean, single-responsibility modules.

[1]: https://github.com/sindresorhus/ama/issues/10#issuecomment-117766328 "Comment by Sindre Sorhus about modular design"

[2]: https://www.poodr.com/ "Practical Object-Oriented Design in Ruby - an excellent book"

[3]: https://yourbasic.org/algorithms/graph/ "Introduction to graph algorithms"

[4]: https://en.wikipedia.org/wiki/Duck_typing "Duck typing on Wikipedia"

[5]: https://en.wikipedia.org/wiki/Interface_segregation_principle "The interface segregation principle on Wikipedia"

[6]: https://www.cl.cam.ac.uk/teaching/1516/L28/parametricity.pdf "Article about parametricity from Cambridge"

[7]: https://medium.com/bigpanda-engineering/understanding-parametricity-in-scala-520f9f10679a "Understanding parametricity in Scala"

[99]: https://sandimetz.com/blog/2016/1/20/the-wrong-abstraction