I didn’t think I will ever write about homework assignments, but this one was too cool. The task: “Write a wrapper class for collections, that reifies all operations on it.” In other words, queries on the collection should be available as AST in order to perform optimizations on them. This post is about one small problem related to the task.
Let’s take a look at a small piece of code, that illustrates the problem.
We have to work on representations of values. Thus,
Rep[T] is a node representing a
value of type
T. It is necessary to define different methods for
Rep depending on the
exact type of
T. For collections we might want to define
map, as for numbers a
Up to now, everything looks fine. How about adding identifiers, that can be both, either
a collection or numeric, depending on it’s type
This isn’t correct for multiple reasons:
- Even, if this would compile the result is not the desired one. An identifier could be used both as collection and numeric, regardless of it’s type.
- It does not compile since
Rep[List[T]]on the type of identifier whereas
Numericsrequires the identifier to be of type
So how can this be achieved?
The Type Constraints Way
The first solution I want to present is based on Scala’s type constraints. They are part
of the Predef and called
=:=. Without digging too deep into the inner workings of those classes, let’s
take a look at the solution first:
The first line is changed just a little. The representation mixes in both traits
Numerics. Both times it provides it’s own type as argument to the type constructors.
In addition to the type argument, a self type annotation is added to the traits. It allows to use
this as instance of
Self within the implementation.
The interesting part is the added parameter list
It says: “Please provide an (implicit) argument, that proves evidence of the subtype relationship between
Rep[List[T]]”. In other words:
Selfhas to be a subtype of
Rep[List[T]]in order to be able to apply the method.
map can only be used on
+ can only be used on
The downside is the additional type parameter on
T). It makes inferring the types for Scala much harder and thus this encoding did not work with for comprehensions.
The “Pimp my Library” Way
The same could also be achieved with a different encoding. The “Pimp my Library” pattern has been invented by Martin Odersky. The pattern is so cool and widely used, that with Scala 2.10 it has built-in language support.
Now, the definition of
Rep[T] is independent of the methods defined on it. This is perfect
for extensibility, since new methods can be added step by step without touching the old
source ever again. Implicit classes are syntactic sugar for defining a class
Wrapper and then adding an implicit definition like
And this is the downside of this approach. Many implicit conversions can make code at user site harder to understand. And it gets worse. Adding an automatic conversion to numerals
does not work well with the other implicit conversions. So we are forced to add the “transitive closure” of implicit conversions by hand:
If you are faced with the problem of adding methods to a type constructor based on it’s type
argument you are free to choose from the solutions presented above. The first one, based on type constraints is not very extensible, since the methods are more or less defined on
Rep itself. It is easier to understand to the user of your API, since the user does not need to see the implicit evidence parameter.
The second encoding, based on the “pimp my library pattern” is more extensible. New methods can
be added without touching old source code. On the other hand it might be hard to understand the implicit conversion magic going on under the hood.
In the end I had to go with the latter one, since it played well with for comprehension syntax and it’s desugaring.