“STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS” COVER / HAHA GUY

How to Trick OO Programmers into Loving Functional Programming

An Intro to Dependency Injection

If you have never heard of dependency injection, this post is not for you. If you have heard of dependency injection, you are probably already writing the opening lines of your hate mail to me.

It’s a narrow topic, but those that know it feel strongly about it.

At its best, DI (thank you acronyms!) is a way to get unstuck from the tar of large-scale object-oriented computer programs. Any seasoned Java engineer can tell you a war story about that time they were only trying to get that FooHelper class from here over to there. And it ended up taking 500 lines of code, because they had to pass FooHelper down a bucket-brigade of 20 different methods in 20 different places. “But with DI: zip! One line! It’s injected!” they insist. “DI makes programming fun again!”

At its worst, DI turns compile-time errors into did-you-just-page-me-at-2AM-you-asshole run-time errors. Everything looks OK. All your tests passed. And then you push your server. Suddenly it’s crashing all the time. You try to debug it. But you can’t figure out where this corrupt FooHelper is coming from because your injector has it squirreled away behind several layers of obfuscation. Or maybe you can’t find your FooHelper at all but no one remembers who was responsible for creating FooHelper in the first place and now you’ve got to go digging through your git history to figure out how you ever had a FooHelper. What Fun!

This post is written for two types of people: those innocent souls who have only vaguely heard about DI (and want to know what the fuss is about), and those jaded souls who are pissed off that their co-workers forced them to use this stupid framework (and just want to know how to find their FooHelpers). I hope it’s helpful to both of you.

Why Dependency Injection?

If you’ve worked on an object-oriented system with more than a few engineers, you have probably noticed your object hierarchies are deep: layers containing layers on top of layers.

HipBone() { this.thigh = new ThighBone() }
ThighBone() { this.knee = new KneeBone() }
KneeBone() { this.leg = new LegBone() }
LegBone() { this.foot = new FootBone() }
FootBone() { this.wiggleDemBones() }

Suppose you want to require socks for your feet. That’s simple! All you have to do is thread the sock through every constructor call.

HipBone(sock) { this.thigh = new ThighBone(sock) }
ThighBone(sock) { this.knee = new KneeBone(sock) }
KneeBone(sock) { this.leg = new LegBone(sock) }
LegBone(sock) { this.foot = new FootBone(sock) }
FootBone(sock) { this.putOnSock(sock); }

You have to modify d lines of code, where d is the depth of your OO hierarchy. I call this the “bucket-brigade” pattern, because every constructor is responsible for passing along dependencies to anyone down the line. In computer science terms, adding the sock argument to all of these constructors is an O(d) algorithm for you, the human who has to type this wiring code. And it’s O(d) places where you could screw up and introduce a bug.

And that’s if you only call each constructor in one place. If you have lots of constructor calls throughout your code, you have to update all of them. Even if you have a refactoring IDE to find all the calls, you still have to find an extra sock to pass in at each call point.

If you’re a functional programming nerd, there’s something else that may bother you about this example. The ‘new’ keyword is weirdly specific:

  1. Allocate some memory
  2. Pass in all the parameters you need to create the object
  3. Return the object immediately 

Why is your LegBone responsible for allocating the memory of your FootBone? Why is he responsible for knowing the initial configuration of his Foot? (Without loss of generality, we assume that all Legs are male.) Why do we need to force a specific order of operations to construct a Leg and a Foot? In this system, Leg has to make a choice between taking responsibility for creating his own Foot, or he has to make his callers responsible for creating a Foot first and passing it in. That’s a frustrating choice.

The DI folks have popularized the view that this is an object graph:

HipBone() -> ThighBone() -> KneeBone() -> LegBone() -> FootBone()

You have a directed graph where each OO-style Object is a node, and the edges of that graph point to the node’s dependencies. This object graph is implicitly represented by the the textual representation of your code. If Leg has a dependency on Foot, then either the Leg is responsible for creating a Foot, or Leg must expose an API where I can pass a Foot in.

When you express the system this way, the problem pops right out. The edge from Foot -> Sock is redundantly encoded. To add 1 new edge in this object graph, you may need to change as many as O(d * k) lines of code, where d is the depth of the object graph, and k is the number of times you need to build a new graph at each level. So a complete graph with N different types of objects might take on the order of k * N^3 lines of code to build. OK, yeah, my formal math is a bit mushy here. But it’s mostly useful to illustrate how the complexity can create super-linear growth in a large program.

What is Dependency Injection?

Dependency injection is a way to make it easier to build and maintain a large object graph. 

Let’s start with a concrete example. Before we go into the details, I want to emphasize one point:

If you want to learn the specific syntax and APIs of a dependency injection framework, there are many great books that will teach you. This post will not. 

I’ve personally used Guice heavily, as well as Shepherd and Spring and Angular lightly. I’m deliberately going to use something that looks mostly like Angular, with bits from Guice and Shepherd, just to make sure I alienate everybody.

HipBone($thigh) { this.thigh = $thigh }
ThighBone($knee) { this.knee = $knee }
KneeBone($leg) { this.leg = $leg }
LegBone($foot) { this.foot = $foot }
FootBone($sock) { this.putOnSock($sock); }
var injector = new Injector()
.add(‘$hip’, HipBone)
.add(‘$thigh’, ThighBone)
.add(‘$knee’, KneeBone)
.add(‘$leg’, LegBone)
.add(‘$foot’, FootBone)
var hip = injector
.using(‘$sock’, new ArgyleSock())
.create(‘$hip’)

Now, don’t freak out. Most people learn DI for the first time when they add a little bit of it in the small corner of their app. And they say, “Hey! This is twice as much code as I would have written otherwise! What a piece of crap!”

Keep in mind that DI is meant to solve a super-linear problem. It does that by adding a layer of abstraction between you and the ‘new’ keyword. If you only use a little DI, you won’t get a lot of benefit for that indirection. The benefits only become obvious when your injector is creating lots of objects, or when you need to make a change.

There are two primary components of any DI system: the injector, and the keys.

The injector is in charge of the object graph. In many cases, it represents this object graph explicitly. It can tell you about every type of object in your program, what other objects it depends on, and how you can create a new one.

The injector indexes these objects by a key. Don’t worry about what a “key” is exactly. That’s not important. Just assume it’s a string (“$sock”) like in our example above.

When you set up your injector, you tell it about all the objects in your program. But you don’t say, “Create a new Hip by creating a new Leg.” You say, “If someone asks for a ‘$hip’, call ‘new Hip($leg)’ with a ‘$leg’ dependency.” In other words, you tell it that a Hip constructor depends on the key ‘$leg’. The Hip shouldn’t have to worry about what kind of Leg it gets: it could get a FleshLeg or a ProstheticLeg. It will use whichever one is registered with the ‘$leg’ key.

It’s easy to write a simple dependency injector in an afternoon. It simply consists of

  1. A set of keys
  2. Each key maps to a dependency description
  3. Each dependency description contains a function to call, and a list of keys of the arguments to this function

When you call injector.get(‘$hip’), your injector looks up the entry for ‘$hip’. It finds the constructor, and the list of keys for its dependencies ([‘$leg’, ‘$leg’], perhaps). For each key, it recursively calls injector.get(key) until it’s created all the arguments. Finally, it creates the hip. 

In an abstract way, the injector is like the Room of Requirement in Harry Potter. You just tell it what you need. The injector will rummage through the bag of functions it has, and figure out how to construct an instance of that object. 

And when you use it for the first time, it’s like magic!

…until you have to debug a problem. Then the cursing begins.

Where Did It Put My Goddamn Call Stacks?

A few paragraphs back, I claimed to you that if you’re spending a lot of time maintaining lists of arguments and “bucket-brigading” dependencies around, that was a good sign your object graphs were redundantly encoded. And that we should try to remove this redundancy.

You should be skeptical of the statement that redundancy in programming languages is always bad. There are many ways in which redundancy is good. Redundancy can help make your code easier to read. If I’m reading a function definition, it would be great if it would tell me the types of its parameters. Sure, this information is also encoded in the callers. If I want to find out the type of the first parameter, I can look at each caller and check what it passes in. But the code is easier to read if that information is encoded twice: at both the function definition and at its callers.

Many languages take the opposite view. “Declared types? We don’t have no declared types. We don’t need no stinking types,” insist languages like Python and JavaScript. But declared types are not the only way that redundant text makes the program easier to read and understand.

  1. Breakpoints let your debugger pause at a particular line of text. If your injector is creating your objects, then there is no “line of text” where the object is directly created. You can’t really use breakpoints to debug the object graph anymore.
  2. Your function throws an exception. It prints a call stack that tells you how it got there. A call stack is just a sequence of lines of text. In a traditional OO program, you get a trace from KneeBone -> LegBone -> HipBone, so you know that the KneeBone failed while constructing a HipBone. In a DI program, that information is built at run-time in the injector. The call stack is just a useless list of internal injector methods.
  3. Your program is failing because the Sock wasn’t set up correctly. Where did this bad $sock come from? In most programs, you can use grep to match up parameters and arguments. In a DI system, the injector creates the argument when it needs it. There’s no line of text where the argument was passed in.
  4. Your injector is failing because it can’t find an entry for $sock. In a compiled language, this would be impossible: the compiler would tell you that you forgot an argument. Even if your language is not compiled, you’d be able to read the caller, tell that an argument is missing, and add it. But in DI-land, dependencies are resolved at run-time. Who was supposed to provide the $sock? Who knows! In a DI system, it’s common for some rarely-used screen of the app to be completely broken due to a missing dependency. The injector won’t tell you about it until the first time someone tries to view that screen.

In short, you’ve probably built up reading and debugging techniques that rely on the structure of the text. In DI, you don’t encode the object graph in the text. You build it at run-time. Your debugging techniques are now useless.

But don’t worry! All hope is not lost. The information you need to debug isn’t in the text. But now the injector knows the complete graph at run-time. And that opens up entirely new possibilities, new debugging paradigms.

This is a rapidly-evolving space. Things that I say about it now might not be true 6 months from now. In general, a good DI framework will provide you with tools for this sort of debugging. I’ve seen DI debuggers where you type in a key, and the injector will tell you all the places that key is used, just like a Java IDE would do with a statically-typed symbol. I’ve even heard talk of DI-aware compilers and IDEs. If you understand how your injector works and the API for its object graph, then you can replace the static-analysis tools that you lost with shiny new dynamic-analysis tools.

With Great Power Comes Something Something

My favorite book on programming is “Structure and Interpretation of Computer Programs,” also known as “The Wizard Book,” or just “S.I.C.P.”

S.I.C.P. advocates strongly for functional programming as a powerful technique. And DI is fundamentally a functional paradigm. 

Your injector is in the business of functions and argument-lists, and treats them as first-class objects to pass around. Now that you’ve given up control of your functions to the injector, your injector has the opportunity to make a lot of the same high-level optimizations that are common in a functional language like Lisp or Haskell.

Suppose you call injector.get(‘$hip’). If it’s naive, the injector can create a new Hip each time. Or, it can give you a Hip from a pre-allocated pool of Hips. Or, if the hip is immutable, multiple callers can share the same hip. Only the return value matters. The injector is free to decide the best way to create a Hip. You don’t have to write your own code for memoizing or managing Hip pools because the injector can do that.

Your injector also has a lot of freedom in how it constructs the Hip dependencies. If it’s naive, it will construct them in serial. But a smart injector can re-order and parallelize the work. If one dependency is going to require disk I/O, and another dependency is going to require network I/O, then the injector can do one while it’s waiting on the other. Or if the injector knows that one dependency is going to be slow to construct, it can kick that one off first.

But if you are not up to snuff on your functional programming skills, this sort of automatic optimization can be a nightmare. Most injectors do not give you a way to specify the exact order the dependencies are constructed in. If you have N dependencies, then your injector may choose one of N! possible orderings. If the providers of your dependencies have side-effects, then you will start running into bizarre non-determinstic errors.

A line from S.I.C.P. is relevant here:

“In general, programming with assignment forces us to carefully consider the relative orders of the assignments to make sure that each statement is using the correct version of the variables that have been changed. This issue simply does not arise in functional programs.” [section 3.1.3, p. 235]

When I first read that, I asked myself, “What kind of doofus screws up the order of assignments?” DI taught me the wisdom in that statement almost 10 years later. Suddenly, you don’t know which order your assignments are going to be applied in. So if Hip changes a property of Leg, and somebody else reads that property of Leg, you may or may not get the wrong value based on whether Hip has been constructed yet.

There are a few ways to work around this problem. One way is to add “fake” dependencies. “I don’t really depend on the result of $x, but I depend on some side-effects of $x, so we’ll just create a fake dependency on $x to resolve the order-of-operations problem.” Other frameworks insist on discipline. You must renounce all the earthly pleasures of mutable types. Any functions you pass to the injector must be pure (i.e. have no side-effects), and must return an immutable dependency. This ensures the problems go away. Still other frameworks lightly encourage you to make your functions pure. If you want to add functions that have side-effects, you need to clearly mark them as such.

Again, this is a space that’s evolving quickly. A lot of the common gotchas in DI are well-understood in functional circles. But a lot of the common benefits are well-understood as well. Some familiarity with functional ideas will help you a lot with DI. 

Variations and Further Reading

Before you explore the wide world of DI frameworks, you should be aware of 2 big variants on the idea.

First, what does an injector look like? Some injectors are rigid: they want you to explicitly register every dependency up-front before they will create any objects for you. The injector will complain loudly if your forgot a dependency. Some injectors are loose. They will let you create an object with some injector-managed arguments and some explicitly-passed-in arguments (sometimes called “Assisted Injection”). Or they will let you change the object graph on-the-fly: “for this object, the ‘$protheticLeg’ key should always be used to satisfy the ‘$leg’ key.”

Some frameworks make the injector a first-class object that is only truly knowable at run-time. You can pass them around, compose them together, inject injectors into other injectors, etc. Other frameworks give you a more restricted API so that they can validate the injector at compile-time, to catch common errors up-front.

Many DI frameworks even let you configure how loose or strict the injector is. You may want to read the API carefully and tailor the injector to your taste.

Second, what does a key look like? In this introduction, we assumed all keys were strings. But that obviously won’t scale very well, because key names will collide. Guice prefers that you use the type name as the key. This is convenient in Java: you need to declare a type anyway, so you might as well let it double as a DI key. If you need 2 different dependencies with the same type, you can create a key from an annotation plus a type name.

JavaScript doesn’t have types, so AngularJS reads the name of the parameter and uses that as the DI key. This is particularly clever, but it means that AngularJS programmers have to adopt strict naming conventions for their DI parameters.

If you’re a Java programmer who wants to read more about how to write DI code, I liked Dhanji Prasanna’s “Dependency Injection” book. It covers a lot of the “nuts and bolts” of the APIs available in Java.

It’s also helpful to read user documentation of a few different DI frameworks. Sometimes, you will also see the phrase “Inversion of Control,” which means the same thing.

Guice (Java)
https://code.google.com/p/google-guice/

Spring’s IoC module (Java)
http://static.springsource.org/spring/docs/3.2.x/spring-framework-reference/html/beans.html 

Dagger (Java)
http://square.github.io/dagger/ 

AngularJS’s DI module (Browser JS)
http://docs.angularjs.org/guide/di 

Shepherd (NodeJS)
https://github.com/Obvious/shepherd

Good luck!