Type Classes

I have been trying to understand type classes for a while and having a hard time figuring out exactly what they mean or how to effectively use them. The idea that they are a means to extend the behavior of a class in a consistent matter makes sense in an abstract way. But I’m not sure how exactly they accomplish that goal, or what a type class is or isn’t. A coworker had offhandedly referred to a type class as “a trait with a type parameter,” but it feels like there has to be more to it than that. This post is a sort of journal of my efforts to figure out exactly what a type class is.

The wikipedia page wasn’t that helpful to me since it defines type classes in terms of other unknown terms. It had one useful tidbit of information from my perspective: in Scala, type classes are implemented with implicits. Following some more links I ended up at the Cats documentation, which has a bunch of example type classes and code using them that I found useful. This got me thinking about whether I had seen anything that had a signature that looked like it might be using a type class. I remembered the sum method on List, which had stuck in my mind because it was unclear as to how it knew how to sum the items and what types it would be legal to sum.

This definitely looks like a type class given our definition so far. We have an implicit argument that is a trait with a type parameter. It is being used to extend numeric types to give them orderings and perform arithmetic operations, but it also signals that the type is numeric. The type class is also being used to constrain what types the sum method is available for, since if the implicit is not available it won’t compile. This constraint also plays nicely with the context bound syntax.

So we’ve got an example and some rules, but that’s not really a definition. I went looking for some more examples in the Cats codebase since that is full of type classes. Each of the individual type classes in Cats definitely follows the pattern of a trait with a type parameter. I think the missing piece for my understanding, lay in what the methods on the type class are. The methods all seem to take at least one argument of the type parameter so that appears to be a reasonable constraint on the functions.

Type classes are different than an implicit class since you can constrain type signatures with it, but they both let you add new functionality to an existing type. The implicit lookup progress imposes some constraints on the implicit class, such as only taking one non-implicit argument, which the type class methods can bypass. You could write an implicit class to expose the type class in a more fluent way like.

 implicit class NumericWrapper[T:Numeric](x: T) {
  def plus(b: T): T = {
    val n = implicitly[Numeric[T]]
    n.plus(x, b)
  }
}

Type classes seem like they would be more useful in a language without multiple inheritance. Since in Scala I can have a type implementing multiple traits that already have implementation associated with them, just mixing in more code seems like an easier way around the extension problems. I found this proposal for adding type classes to C#, which seems very cool and in line with the sorts of powerful abstractions they’ve been trying to add to the language. Seeing a different syntax for using type classes without implicits being involved helped me understand what they really are.

Going back to my initial goal of figuring out what a type class is and how it works, I think I’ve figured out both. It is a generic type that adds functionality to that type but defers the implementation of that functionality. Then you specify something that expects the type class and brings the implementation of the functionality and the data together. In Scala it accomplishes this using type bounds to specify the type class and implicit parameters to pass the type class into the implementation. I’m still not sure when I would want to write my own type class as opposed using other polymorphic concepts, but I’m now confident about using existing type classes and even breaking out some of the Cats-based ones as opposed to just some of the inbuilt ones.

Advertisements

Book Chat: Programming in Scala

I had previously mentioned Programming in Scala when discussing Scala for the Impatient, saying that Scala for the Impatient was written as a reaction to the ~800 page bulk of Programming in Scala for people who wanted just enough to get started with. After having read Programming in Scala it feels like criticism of its length is fair. The first half of the book was massive overkill for people who had experience in any C derived language or any other sort of object oriented language. There were sections that were marked off as optional reading  if you were familiar with Java because the behavior being described was similar. In comparison, the second half of the book was a wonderful experience even for an experienced programmer, since there were in depth explanations of all of the advanced language features.

Some of the things I learned were simple. For instance, that regular expressions can be used as extractors, which is a straightforward idea. Or, that predef is implicitly imported everywhere. Or that the arrow operator is actually defined as an implicit conversion in predef and not an explicit part of the language.

Other sections were more complex. The rules for how for expressions get mapped into other syntax were similar to what I had figured out, but the rule about how conditionals and assignments within the expression are evaluated added a lot of clarity to what I had learned by doing. I learned the ways you can use type bounds to improve variance indicators. The authors also discussed the transform method on futures that will be available in Scala 2.12, which has me excited to get to that upgrade.

There were some other things covered that even after a considerable study I’m not sure I understand. I understand the syntax for refinement types but I don’t think I understand the value even after the provided in-depth example using currencies. There was also an in-depth discussion of how the designers arrived at CanBuildFrom in the collections package. CanBuildFrom enables extraction of common operations from many collections but returns a collection of that same type and not some supertype. It makes sense in an abstract sense, but I don’t think I could implement a similar pattern without copying it directly out of the book.

Despite the book’s heft, there were a couple of topic I would have liked to know more about. I was hoping for a discussion of the reflection capabilities provided by manifests, type tags, and class tags, but since they are just library pieces and not integral to the language they weren’t covered. There were some oblique references to how bytecode gets generated from various Scala structures, but I was hoping for more insight into how to make interfaces that are less susceptible to breaking changes under the hood even when the Scala side looks fine.

Overall it’s a good read and not as long to read as you would think a book this size would be. It’s easily divided up into small sections so you can easily sit down and read a page or two and make progress over time.

Continuation Passing Style

I have been doing some work with a library that creates guards around various web endpoints. They have different kinds of authentication and authorization rules, but are all written in a continuation passing style. The idea of the continuation passing style is that you give some construct a function to ‘continue’ execution with once it does something. If you’ve ever written an event handler, that was a continuation. The usages all look somewhat like

secureActionAsync(parseAs[ModelType]) { (userInfo, model) => user code goes here }

There was some discussion around whether we wanted to do it like that or with a more traditional control flow like

secureActionAsync(parseAs[ModelType]) match {
    case Allowed(userInfo, model) => user code goes here then common post action code
    case Unallowed => common error handling code
}

The obvious issue with the second code sample is the need to call the error handling code and post action code by hand. This creates an opportunity to fail to do so or to do so incorrectly. The extra routine calls also distract from the specific user code that is the point of the method.  

There were some additional concerns about the testability and debuggability of the code in the continuation passing style. The debugging side does have some complexity but it isn’t any more difficult to work through than a normal map call which is already common in the codebase. The testability aspect is somewhat more complex though. The method can be overwritten with a version that always calls the action, but it still needs to do the common post action code. The common post action code may or may not need to be mocked. If it doesn’t need to be mocked this solution works great. If the post action code needs to be mocked then putting together a method that will set up the mocks can simplify that issue.

This usage of a continuation helps collect the cross cutting concern and keeps it all on one place. You could wrap up this concern other ways, notably with something like like AspectJ. The issue with doing it with something like AspectJ is that it is much less accessible than the continuation passing style. AspectJ for this problem is like using a bazooka on a fly, it can solve it but the level of complexity introduced isn’t worth it.

Future[Unit] Harmful

I’m not the first person to have seen this behavior but I saw it bite another engineer recently so it’s clearly not well enough known. The Unit type in Scala is a special type, there is effectively an implicit conversion from every type to Unit. If you are interested in the specifics check out this post, I’m not going to get into the specifics of how it works or the edge cases. This means that you can write the something like

val doubleWrapped: Future[Unit] = Future.successful(Future.successful(true))

and that compiles. It breaks the type safety that we have come to expect. More intriguingly if you were to do

val innerFailure: Future[Unit] = Future.successful(Future.failed(new RuntimeException))
innerFailure.value

what would you expect the result to be?

If you said

Some(Success(()))

you would be right, but that would probably not be what you were looking for. If you had a map where you needed a flatMap you would end up with compiling code that silently swallows all error conditions. If you have an appropriate set of unit tests you will notice this problem, but you can have that code that looks simple enough that it doesn’t need any unit tests.

The compiler flag -Ywarn-value-discard should give you some protection, but you need to turn it on explicitly and it may produce a fair bit of news in an existing large codebase. So keep an eye out for this issue, and be forewarned.

Tagging in Macwire and Type Currying

We’ve been using the Macwire dependency injection framework and I recently got to use the tagging functionality for the first time. This was a great feature that enabled me to instantiate multiple instances of the same type and have the framework differentiate between the instances when choosing which to inject.

First, you define a trait to be the marker; it doesn’t need anything in it. Then, at the injection site it becomes

BaseType @@ Marker

When setting up the initial site, instead of being

wire[BaseType]

it becomes

wire[BaseType].taggedWith[Marker]

That’s all there is to the base case. You can chain multiple tags in a couple of different ways.

wire[BaseType].taggedWith[Marker].andTaggedWith[OtherMarker]

or

wire[BaseType].taggedWith[Marker with OtherMarker]

 

I combined all of this with another neat construction of the type system.

trait Foo[Marker](dependency:Bar @@ Marker)

Once I set up the Foo type like this it lets me take a marked dependency in a generic way.

I would like to see some sort of syntax like

preference[Marker].wire[BaseType]

So I don’t need to make changes to the type being instantiated in order to control the preference of what instance gets supplied. There is also the module syntax, where you can create a module for each set and then nest those modules to get the injections as desired; but I don’t want to have to organize my code in a specific way in order to have it work correctly.

All of this had me thinking about currying/partial application and the application of generic types. You can take a type with multiple generic parameters and apply some of them and leave the rest for later. It’s not something that happens often but it came to mind with the way I was using generic types there and it was an interesting insight into the symmetry between types and data.