Making Typed languages work for you

A story about Scala, expressive type systems, and the MTA

As our software programs grow, so do their complexity. Inevitably, it becomes almost impossible to wrap your head around all the moving parts. But fear not! There are some common practices and useful tools that we can use in order to keep our codebase easier to reason about. In this blog post, we’ll be using scala (version 2.12.7) and its expressive type system to solve some problems with the MTA’s New York City Subway.

Now a little about the MTA

Believe it or not, the MTA can help teach us a bit about code, but before we dive in, we need a little history lesson. The MTA is the amalgamation of three different companies: the Interborough Rapid Transit company (IRT), the Brooklyn-Manhattan Transit Corporation (BMT), and the Independent Rapid Transit Railroad (IND). The BMT and the IRT were privately owned companies purchased by the city of New York in 1940, while the IND was commissioned by the city of New York. In 1953, the New York City Transit Authority was created to oversee operations on all three lines. If you want to learn more about the history of the MTA, you can find it here and here.

Now the really interesting thing about all of this is that the tunnels that each company created were of different sizes. A BMT train is wider than an IRT train and, therefore, while an IRT train can go through a BMT tunnel, a BMT train could never go through an IRT tunnel. With this in mind, let’s imagine that the MTA has commissioned us to write a program that manages their routing (let’s be honest, they need all the help that they can get). We know that in creating our program, we can never allow a train that was meant for the BMT to run through an IRT Tunnel, but an IRT train can go through both an IRT and BMT tunnel. Think we can do it?

Let’s do some modeling

The answer to that is of course we can! Now let’s think about what we need in order to create our system. At the very least, it seems that we need two models: Trains and Tunnels (note: there are probably way more things to consider, but to get started I think these two models will suffice). So what do we know about the trains? Well, I think that it is safe to assume that all trains should be able to travel. We also know we’ll be dealing with two different types of trains: IRT trains and BMT trains. Remember: a BMT train can only travel through BMT tunnels, but a IRT train can travel through both tunnels. It would be awesome if there was a way to know what train could be substituted with the other. Fortunately there is! Time to learn a bit about subtyping.

Subtypes for the Subway

According to Wikipedia, if S is a subtype of T, then any term of type S can be safely used in a context where a term of type T is expected (note: the subtyping relation is often written S <: T). Let’s try to apply this to our example to make it more concrete. We can think about the BMT as the T (type) and the IRT as the S (subtype), because in our example, an IRT train can safely be used in any context that a BMT train can be used. The relationship is not reciprocal; we cannot use a BMT train where IRT trains run. The BMT trains are too wide to go through IRT tunnels, so we can’t safely route them through the same tunnels. Awesome, this is enough information to define the relationship between the two trains.

package train { 
     
     abstract class Train { 
        def travel: Unit 
     }
     class BMT extends Train { 
         override def travel = { 
            println(“Traveling on the BMT”) 
         } 
     }
     class IRT extends BMT { 
         override def travel = { 
             println(“Traveling on the BMT or the IRT”) 
         } 
     } 
}

As you can see, both trains implement the same exact interface. The only difference is that while the BMT class inherits from our abstract Train class, the IRT class inherits from the BMT class. This is because we want to be able to safely substitute IRT trains for BMT trains according to the subtyping principle from earlier. Awesome, now that the trains are modeled, let’s create the tunnels.

Just a generic tunnel

For our tunnels, we are going to make use of generics. So what are generics? Generics are classes that take another class as a parameter. Let’s take a list for example. A List is a generic type that holds onto another type. You can have a list of Integers, Strings, or AnyData type you want really. In our case, we want our generic Tunnel to hold onto a Train type. Now that we understand generics a bit, let’s build our tunnel.

import train.Train
package tunnel { 
 class Tunnel[T <: Train](trains: List[T]) { 
    def schedule = { 
      trains 
    } 
  } 
}

This is a pretty short file, but there is a lot going on here. Let’s break it down. We define our class, but it has some pretty weird syntax. What’s this <: thing? It’s actually pretty simple. We are giving an instruction to the compiler that is saying when we are creating a new Tunnel, the types that can be associated with it are Train types and Train subtypes. This means that if we created a Car class like this…

class Car { 
  def travel = { 
    println(“Traveling in a car”) 
  } 
}

…an instance of this Car class would still not be able to go through any of our tunnels because a Car does not extend the Train interface.

Lastly, our tunnel class gets instantiated with a list of trains and has a method schedule that returns to us the list of trains. This is pretty much all we need to know for now in order to start routing the trains through the tunnels properly!

Putting it all together

Now that we have our trains and our tunnels, it is time for us to do some routing. The goal is to be able to schedule trains through tunnels and not have any accidents when the trains start running (or at runtime!). Let’s see if we can do it. First, let’s create some trains:

val bmt = new BMT 
val irt = new IRT 
val trains = List(bmt, irt)

Now that we have our list of trains, let’s create a tunnel. We see that we have both a BMT train and a IRT train to schedule. The only type of Tunnel that can accommodate both IRT and BMT trains is a BMT Tunnel, so let’s create one and give it our list of trains.

val bmtTunnel = new Tunnel[BMT](trains = trains)

If we try to run this in the scala console, we get the following:

scala> val bmtTunnel = new Tunnel[BMT](trains = trains) 
bmtTunnel: Tunnel[BMT] = Tunnel@5973e4ec

So far so good, but just to be sure, let’s check that our scheduled trains can actually travel.

scala> bmtTunnel.schedule.foreach(_.travel) 
Traveling on the BMT 
Traveling on the BMT or the IRT

Awesome, our trains are running as we expect them to. What would happen if we tried to route BMT trains through an IRT tunnel? Let’s try it and find out, hope we don’t cause an accident!

scala> val irtTunnel = new Tunnel[IRT](trains = trains) 
:14: error: type mismatch; found : List[BMT] required: List[IRT] val irtTunnel = new Tunnel[IRT](trains = trains) ^

Great! We can’t create an IRT tunnel and give it the list of IRT and BMT trains at all. Our pair programming partner, the compiler, tells us that the list of trains do not match the type expected for an IRT tunnel. But why are we getting a List[BMT] type when we passed in both IRT and BMT trains? The reason is because when scala gets a list of mixed types, it tries to find the most specific type tied to all the elements of the List. In our case, the most common type between our two train types is the BMT type, since we had decided earlier that our IRT trains extend the functionality of the BMT trains. Thus, scala infers the type of our list to be List[BMT]. Let’s fix this and give our tunnel some trains that it can actually schedule.

val irtTrains = List(new IRT, new IRT) val irtTunnel = new Tunnel[IRT]

Now let’s run our trains through our tunnel:

scala> irtTunnel.schedule.foreach(_.travel) 
Traveling on the BMT or the IRT 
Traveling on the BMT or the IRT

Nice! And just for the sake of thoroughness, let’s try to route a list of only IRT trains through a BMT tunnel. We should be able to do this with no problem.

scala> val newBmtTunnel = new TunnelBMT newBmtTunnel: Tunnel[BMT] = Tunnel@3344c1d7
scala> newBmtTunnel.schedule.foreach(_.travel) 
Traveling on the BMT or the IRT 
Traveling on the BMT or the IRT

We did it! We helped the MTA route the trains. Surely this will help with all the delays and help everyone to get where they are going on time.

The Rap Up

We went over a lot of concepts today, so let’s recap. We used scala to model the trains and tunnels of the MTA, taking careful considerations about the different types of trains and tunnels that can exist in this system. We touched on topics such as Liskov’s Substitution Principle as well as variance, which ultimately tell us when it is okay to substitute one type for another.

This is just a taste of some of the tools that a language like scala can offer a developer. Applying constraints to our models allows us to build out new functionality without fear of breaking compatibility, because the compiler will tell us that we are doing something that is making our program unsound. It can help to make your impossible states impossible, which takes the mental load off you when you are developing your application.

Thanks for reading! Want to work on a mission-driven team that loves expressive type systems and public transit? We’re hiring!

To learn more about Flatiron School, visit the website, follow us on Facebook and Twitter, and visit us at upcoming events near you.

Flatiron School is a proud member of the WeWork family. Check out our sister technology blogs WeWork Technology and Making Meetup.