Tuesday, August 10, 2010

Using generalized type constraints - How to remove code with Scala 2.8

I love removing code. More I remove lesser is the surface area for bugs to bite. Just now I removed a bunch of classes, made unnecessary by Scala 2.8.0 type system.

Consider this set of abstractions, elided for demonstration purposes ..

trait Instrument

// equity
case class Equity(name: String) extends Instrument

// fixed income
abstract class FI(name: String) extends Instrument
case class DiscountBond(name: String, discount: Int) extends FI(name)
case class CouponBond(name: String, coupon: Int) extends FI(name)

Well, it's the instrument hierarchy (simplified) that gets traded in a securities exchange everyday. Now we model a security trade that exchanges instruments and currencies ..

class Trade[<: Instrument](id: Int, account: String, instrument: I) {
  def calculateNetValue(..) = //..
  def calculateValueDate(..) = //..

In real life a trade will have lots and lots of attributes. But here we don't need them, since our only purpose here is to demonstrate how we can throw away some piece of code :)

Trade can have lots of methods which model the domain logic of the trading process, calculating the net amount of the trade, the value date of the trade etc. Note all of these are valid processes for every type of instrument.

Consider one usecase that calculates the accrued interest of a trade. The difference with other methods is that accrued interest is only applicable for Coupon Bonds, which, according to the above hierarchy is a subtype of FI. How do we express this constraint in the above Trade abstraction ? What we need is to constrain the instrument in the method.

My initial implementation was to make the AccruedInterestCalculator a separate class parameterized with the Trade of the appropriate type of instrument ..

class AccruedInterestCalculator[<: Trade[CouponBond]](trade: T) {
  def accruedInterest(convention: String) = //.. impl

and use it as follows ..

val cb = CouponBond("IBM", 10)
val trd = new Trade(1, "account-1", cb)
new AccruedInterestCalculator(trd).accruedInterest("30U/360")

Enter Scala 2.8 and the generalized type constraints ..

Before Scala 2.8, we could not specialize the Instrument type I for any specific method within Trade beyond what was specified as the constraint in defining the Trade class. Since calculation of accrued interest is only valid for coupon bonds, we could only achieve the desired effect by having a separate abstraction as above. Or we could take recourse to runtime checks.

Scala 2.8 introduces generalized type constraints which allow you to do exactly this. We have 3 variants as:
  • A =:= B, which mandates that A and B should exactly match
  • A <:< B, which mandates that A must conform to B
  • A A <%< B, which means that A must be viewable as B

Predef.scala contains these definitions. Note that unlike <: or >:, the generalized type constraints are not operators. They are classes, instances of which are implicitly provided by the compiler itself to enforce conformance to the type constraints. Here's an example for our use case ..

class Trade[<: Instrument](id: Int, account: String, instrument: I) {
  def accruedInterest(convention: String)(implicit ev: I =:= CouponBond): Int = {

ev is the type class which the compiler provides that ensures that we invoke accruedInterest only for CouponBond trades. You can now do ..

val cb = CouponBond("IBM", 10)
val trd = new Trade(1, "account-1", cb)

while the compiler will complain with an equity trade ..

val eq = Equity("GOOG")
val trd = new Trade(2, "account-1", eq)

Now I can throw away my AccruedInterestCalculator class and all associated machinery. A simple type constraint tells us a lot and models domain constraints, and all that too at compile time. Yum!

You can also use the other variants to great effect when modeling your domain logic. Suppose you have a method that can be invoked only for all FI instruments, you can express the constraint succinctly using <:< ..

class Trade[<: Instrument](id: Int, account: String, instrument: I) {
  def validateInstrumentNotMatured(implicit ev: I <:< FI): Boolean = {

This post is not about discussing all capabilities of generalized type constraints in Scala. Have a look at these two threads on StackOverflow and this informative gist by Jason Zaugg (@retronym on Twitter) for all the details. I just showed you how I removed some of my code to model my real world domain logic in a more succinct way that also fails fast during compile time.

Update: In response to the comments regarding Strategy implementation ..

Strategy makes a great use case when you want to have multiple implementations of an algorithm. In my case there was no variation. Initially I kept it as a separate abstraction because I was not able to constrain the instrument type in the accruedInterest method whole being within the trade class. Calculating accruedInterest is a normal domain operation for a CouponBond trade - hence trade.accruedInterest(..) looks to be a natural API for the context.

Now let us consider the case when the calculation strategy can vary. We can very well extract the variable part from the core implementation and model it as a separate strategy abstraction. In our case, say the calculation of accrued interest will depend on principal of the trade and the trade date (again, elided for simplicity of demonstration) .. hence we can have the following contract and one sample implementation:

trait CalculationStrategy {
  def calculate(principal: Int, tradeDate: java.util.Date): Int

case class DefaultImplementation(name: String) extends CalculationStrategy {
  def calculate(principal: Int, tradeDate: java.util.Date) = {
    //.. impl

But how do we use it within the core API that the Trade class publishes ? Type Classes to the rescue (once agian!) ..

class Trade[<: Instrument](id: Int, account: String, instrument: I) {
  def accruedInterest(convention: String)(implicit ev: I =:= CouponBond, strategy: CalculationStrategy): Int = {

and we can now use the type classes using our own specific implementation ..

implicit val strategy = DefaultImplementation("default")
val cb = CouponBond("IBM", 10)
val trd = new Trade(1, "account-1", cb)
trd.accruedInterest("30U/360")  // uses the default type class for the strategy

Now we have the best of both worlds. We implement the domain constraint on instrument using the generalized type constraints and use type classes to make the calculation strategy flexible.


Kafecho said...

Thanks for the post, that is very useful. Looking forward to reading the DSL in Action book too.

joe said...

Interesting things these constraints, thanks for bringing this up - where could one learn the new 2.8 features (and some advanced pre 2.8) systematically?

I don't know anything about the domain - so the following might not be necessary. But its seems as if you now moved the strategy (for calculation) back into the class. And you cant overload the implicit (implicit ev: I =:= OtherBond): (I guess ?). So whenever you want another accruedInterest with this trade but with another Instrument, you have to create a method with a different name, instead of a new class as was before. Did you really gain a lot?

Debasish said...

@joe accrued interest is only applicable for coupon bonds - that's one of the domain assumption in my case. You r correct .. if I had to do some polymorphic stuff, a separate abstraction would have been better. But here it's not the case - so it sets up nicely with the =:= type class that Scala 2.8 offers.

Sam Stainsby said...

Fantastic! I wasn't aware of this feature. Like others I don't fully understand the domain though.

Eric said...

This kind of post is really, really valuable because it shows the relevance of Scala in a real-world setting (who said that Scala was an academic-only language :-)?).

My only comment would be along what Joe wrote: "its seems as if you now moved the strategy (for calculation) back into the class".
It is fairly likely that on a real-world project doing so will clutter your Trade class and bring on more and more dependencies on that class.

So I think that a short update showing how you can re-extract that logic to a "pimped" Trade class, with an implicit definition using the same kind of generalized type constraint and leaving the client code untouched would be useful (which bring us back to a TypeClass pattern doesn't it?).

Isn't it what you will eventually do on your real project?

martin said...

Very nice post! I have just one small point to add. Generalized type constraints are in no way ``magical'', the compiler knows nothing about them. There are just these three classes in Predef: :<, <%<, =:= together with implicit definitions that give you the roper instances. If you want to rename them to something like conformsTo, visibleAs, equalTo, you can, and things will work the same way.

So anyone could have written these classes, it's not that they are burned into the language.

The new thing in 2.8 is that implicit resolution as a whole has been made more flexible, in that
type parameters may now be instantiated by an implicits search. And that improvement made these classes useful.

That's what I call a sweet spot in language design. You make an existing feature stronger and you get another one for free (the only other treatment of generalized type constraints I know of is Kennedy and Russo's work which appeared at OOPSLA 04. This was proposed, but to my knowledge never accepted, for C#).

james-iry said...

BTW, prior to 2.8 the idea could more or less be expressed with

def accruedInterest(convention: String)(implicit ev: I => CouponBond): Int = ...

I say more or less because ev could be supplied by any implicit function that converts I to CouponBond. Normally you expect ev be the identity function, but of course somebody could have writen an implicit conversion from say DiscountBond to CouponBond which would screw things up royally.

To reiterate what Martin said, here's the definition of the =:= class


And here's the definition of the implicit that supplies instances of it.


No compiler magic that you can't use yourself.

Cedric said...

Couple of comments:

1) The fact that the generalized type constraints are identifiers and not operators seem like a compiler technicality that users should not be exposed to. My naive reaction the first time I read about ":<:" was "why didn't they reuse ":<" since the meanings are so close to each other?

2) I don't know if it's your example or the concept, but it feels like your nicely generic class Trade has now been polluted with a specific implementation. This doesn't smell too good to me, but maybe I'm missing something?

Debasish said...

Hi Cedric -

Thanks for visiting my blog. Addressing your second concern ..

Which specific implementation are u talking about ? Is it that of accruedInterest method ? AS I mentioned, if we can have only ONE implementation of the method, why can't we have it within the Trade class ? And if we have any variation, then we can refactor the variable part in the form of a strategy class. I have done exactly this in the update which I posted yesterday. Please have a look at the bottom of the post where I discuss this.

Would be willing to know your thoughts.

Cedric said...

Debasish, I'm talking about CouponBound. Before you introduced the generalized type constraint, your Trade class was relying on the very generic Instrument class, and that was great.

After the type constraint, your interface is now coupled with a subclass (or an implementation) of Instrument.

This sounds like an implementation detail that should be handled with an instanceof internally instead of leaking into the interface and coupling your class with an implementation.

As for my first point: still no answer? Would you agree that :< would be acceptable instead of :=: or am I missing something?

Debasish said...

Hi Cedric -

First let me address the issue with Coupon Bond. I agree that CouponBond is a specific implementation of Instrument.
At the same time the method accruedInterest is ONLY applicable for CouponBonds only. No other instrument type can have accrued interest. This is a domain constraint, which I need to express. In terms of the Trade abstraction, it turns out to be "A CouponBond trade needs to calculate the accrued interest". So in the problem domain itself there's a coupling between Trade and CouponBond.

What you have suggested is to keep the Trade abstraction *completely* generic without any coupling with implementation classes. That's what I did in the first implementation. The flip side however, is that the APIs are not always that intuitive. An accrued interest calculation is an innate component of a CouponBond trade valuation. Hence an API like
trade.accruedInterest(..) looks more natural than new AccruedInterestCalculator(..).accruedInterest(trade). It's just a
matter of taste I guess - I don't mind to couple an abstraction with some implementation if the problem domain model itself has such a coupling. And the generalized type constraints allow me to do that quite succinctly. However if I have variations within the implementation, then of course I need to refactor that in a Strategy, as I have shown in
the update to the post towards the end.

Now regarding your first concern, I agree that both <: and <:< has a similar underlying connotation of conformance. I think the designers chose a different symbol only to differentiate the fact that <: denotes an upper bound in a type
constraint, while <:< is actually a class in Predef. As Martin has indicated in his comment to my post, you could very well rename it to conformsTo instead of <:<. Also I am not sure if there would be any parser issue if they used the same
symbol for both cases.

Debasish said...

Hi Martin / James -

Thanks for the very clear explanation. It's really great that these type constraints are plain Scala classes and NOT burned into the language core. Plus the improved implicit resolution in 2.8 has made them more potent in designing intuitive APIs (as I have demonstrated with a real world example).

Debasish said...

Hi Kafecho -

Glad that you liked the post. Great to hear your comments on the book too. I hope you like it.

martin said...

Debashish, Cedric,

The reason we could not use <: and <% is that these are reserved (i.e. keywords). As I have explained above, <:< and <%< are user-defined. So we could not have taken the same operators for them. It's like insisting hat you should use `if' for a conditional construct in a DSL - yes it would be nice if you could reuse `if' in that context, but unfortunately you can't.