prose :: and :: conz


A dab of recursion will do

Last week I lamented some flaws I had run into with Scala’s static typing while working on SNMP4S. Thanks to the venerable Paul Snively, his retweet attracted some friendly commenters. With their input I now I know how to solve the problem in the confines of good static typing. That’s the good news. The bad news is I was wrong and all of Snively’s followers know this Joe Barnes guy is a moron. I’m sure it hasn’t run my most faithful audience member (Hey Mom!) away from my blog, tho.

The solution is awesome. It turns out that I just need a little recursion to roll all of my types into an arbitrarily-deep nesting of Tuple2’s. If you’ve been following my Static typing doesn’t have to suck series, this post will tie together many of the features I’ve covered.

Lets work through an example. Suppose I want to grab the following three objects from an SNMP agent, which are typed as an integer, octet string, and enum respectively. This is how I would have written it previously:

val res:(Int, String, ifAdminStatus_enum.Value) = 
  get(IfSpeed(1), IfName(1), IfAdminStatus(1))

As you can see, this response is a Tuple3 (*Note: In SNMP4S it’s actually 3 Either[SnmpError,T]‘s but for the sake of this discussion, I’m leaving that out). This approach is limited to a max of 22, and it requires me to explicitly write (or generate) 22 overloads of the get() method. That sucks. But it doesn’t have to be that way! Instead, we first should consider trying to make this an embedding of a Tuple2 inside another Tuple2: (Int, (String, ifAdminStatus_enum.Value)). This then can be made arbitrarily deep avoiding the 22 limit. For instance, if you had four integer objects, the return type would be (Int, (Int, (Int, Int))).

We can’t just go straight to that solution. We need a data structure to hold the object and build these types. Let’s create a GetRequest container. We will implement it similarly to Scala’s (linked) List. That is, we will have a GetRequest trait and some case class implementations. First, the GetRequest:

sealed trait GetRequest[T]

The type parameter T will correspond to the type of the object being requested. Since we don’t have a need for an empty GetRequest, I’ll ignore the Nil case and use a request with a single object as my base case:

case class SingleGetRequest[A <: Readable, T]
  (val obj:DataObject[A, T]) 
  extends GetRequest[T]

Here you can see where the type parameter T is related to our DataObject class, as well as how we ensure that only Readable objects are allowed. Next we need our container for the case of a list with more than one item. As I hinted at before, we will use a linked list approach. That is, our case class will have an object that is the head of the list and a reference to the tail of the list. The good part is in the type annotations where we make our tuple:

case class CompoundGetRequest[A <: Readable, T, U]
  (val head:DataObject[A, T], val tail:GetRequest[U]) 
  extends GetRequest[(T, U)]

Now I can build my get request:

val req = CompoundGetRequest(IfSpeed(1), 
  CompoundGetRequest(IfName(1), 
  SingleGetRequest(IfAdminStatus(1))))

Each time we create a CompoundGetRequest, the type parameter U is getting set to whatever mess of Tuple2’s we’ve brought along, or just the type of the DataObject if working with a single request.

But isn’t that code ugly? Absolutely. This is where we get to have fun with Scala’s support for operator creation. Rather than explicitly create each CompoundGetRequest, I’ll create an operator on GetRequest that will do it for us:

sealed trait GetRequest[T] {
  def &[A <: Readable, U]
    (obj:DataObject[A, U]):GetRequest[(U, T)] =
    CompoundGetRequest(obj, this)
}

Then our GetRequest looks a little better:

val req = SingleGetRequest(IfSpeed(1)) & IfName(1) & IfAdminStatus(1)

Now let’s get rid of the initial SingleGetRequest. Since it’s essentially a wrapper for one of our objects, an implicit conversion will work very well.

implicit def DataObject2GetRequest[A <: Readable, T]
  (obj:DataObject[A, T]):GetRequest[T] = SingleGetRequest(obj)

Now we can write this code:

val req = IfSpeed(1) & IfName(1) & IfAdminStatus(1)

One more hang up. The list is getting built backwards. Look at the inferred type:

req: org.snmp4s.GetRequest[
  (org.snmp4s.IfMib.IfAdminStatus_enum.Value, (String, Int))]

This is happening because the & operator is getting called on the left item and passing it the right item. What we want is the opposite. Scala has a solution for that, too. Any method that ends in a colon is right-associative, meaning it gets called against the object on the right, passing it the object on the left. So let’s update our operator and look at the inferred type.

def &: (...)
val req = IfSpeed(1) &: IfName(1) &: IfAdminStatus(1)
req: org.snmp4s.GetRequest[
  (Int, (String, org.snmp4s.IfMib.IfAdminStatus_enum.Value))]

Now we’re looking pretty good. However, this is only half of the story, right? We still need a way to extract the result of the get() query. My initial thought is to mirror the GetRequest hierarchy with a GetResponse hierarchy like so:

sealed trait GetResponse[T] 
case class SingleGetResponse[T]
  (val res:T) 
  extends GetResponse[T]
case class CompoundGetReponse[T, U]
  (val head:T, val tail:GetResponse[U]) 
  extends GetResponse[(T, U)]

(Again, the type of res is actually res:Either[SnmpError,T], but I’m omitting that detail for clarity)

However we’re still somewhat in the state we were before with the GetResponse. We have this big ugly thing we have to match against:

get(IfSpeed(1) &: IfName(1) &: IfAdminStatus(1)) match {
  case CompoundGetResponse(v1, 
    CompoundGetResponse(v2, 
    SingleGetResponse(v3))) => 
  case _ =>
} 

This one is actually pretty easy to fix. We just rename our CompoundGetResponse to an operator. This will let us do a match against it.

case class &: (...)
get(IfSpeed(1) &: IfName(1) &: IfAdminStatus(1)) match {
  case &:(v1, &:(v2, SingleGetResponse(v3))) 
  case _ =>
} 

But we want this to be an infix operator so it looks the same as the call to get(). The cool thing is that case classes can be written in infix notation when part of a pattern match:

get(IfSpeed(1) &: IfName(1) &: IfAdminStatus(1)) match {
  case v1 &: v2 &: v3 =>
  case _ =>
} 

Ok, so if you try this code, you’ll see it’s not quite perfect. The last matching variable v3 will actually be a SingleGetResponse[T]… It doesn’t unwrap for you. Now, I have been simplifying the code for this discussion by ignoring how I’ve wrapped all responses as Either[SnmpError, T]. The good news is I can have an implicit conversion from Either[SnmpError, T] to SingleGetResponse[T]. The bad news is, it won’t work in pattern matching until Scala 2.11.

While all of this is great, I’m a little hung up. I would like to use the same operator in both lists. Each of these request/response objects can in fact define &:, but only one case class can exist. Given the way I’ve defined everything thus far, I can only pattern match against the GetResponse list. Somehow I need yet another higher level of abstraction to say that the heterogenous list contains the DataObject[A <: Readable, T] types versus the Either[SnmpError, T] result types. I also have some other types I’ll need to collect for my set request/responses. Hopefully I’ll figure it out one day. If you have some good ideas, please leave them in the comments.


Olde Comments
  1. noootsab says:

    Cool stuffs here!
    For the &: class, maybe add a new abstraction over GetRequest and GetResponse might work (didn’t tests… just thinking out of loud ^^):

    sealed trait Get[R, H[T], T]

    sealed Request
    sealed Response

    sealed trait GetRequest[T] extends Get[Request, {type λ[U] = DataObject[_, U]}#λ[T], T]{
    def &:[A <: Readable, U]
    (obj:DataObject[A, U]):GetRequest[(U, T)] =
    CompoundGetRequest(obj, this)
    }
    sealed trait GetResponse[T] extends Get[Response, {type λ[U] = Either[SnmpError,U]}#λ[T], T]

    case class &:[H, R, T, U, G <: Get[R, H, T]](val head:H, val tail:Get[R, H, U]) extends Get[R, (T, U)]

    BTW, nice blog!

    • barnesjd says:

      Thanks! I enjoyed writing.

      So I see you’re using some λ stuff. Perhaps that’s what I was missing. I’ve been trying to do the sort of abstraction you’re talking about, but I’m at a loss. Do you have a good reference where you learned how to use that?

  2. Indeed it’s very helpful.
    I don’t really have reference for that but maybe I can try to give you an intuition about where it helps… (I’ll try to express myself correctly ^^)

    Actually the lambda trick is needed when a type A relies on another type which is a type constructor B with one type parameter (B[_]).

    For instance Functor[F[_]], an instance of such Functor would be Functor[Option]. This works because the F type and Option match (1 type parameter).

    But what if you want a Functor of Either? Since Either is a type constructor with 2 type parameters, Functor[Either] won’t compile, so we need to convert Either to another type constructor matching the requirement. Let’s say we choose Either to be right biased (as usual), to generate the required type constructor we still need to fix the left side :-/.

    So, on very simple solution, would be to create Functor instances by left type for Either

    type EitherStringOr[T] = Either[String, T]
    type EitherDoubleOr[T] = Either[Double, T]

    then,
    object EitherStringFunctor extends Functor[EitherStringOr]
    object EitherDoubleFunctor extends Functor[EitherDoubleOr]

    But it will be very complicated to create all of them… right?

    So another solution would be to create the type constructor on the fly this way:

    case class EitherFunctor[E,A] extends Functor[{type λ[U] = Either[E,U]}#λ]

    That is, we create an structure (using {}) containing only one type (λ) that reuse the type E for the left hand side, and has itself a type parameter (U). Then we extract this λ type out the inline structure using #.

    So now, we can create usual functor builders this way

    implicit def eitherStringFunctor[A] = EitherFunctor[String, A]
    implicit def eitherDoubleFunctor[A] = EitherFunctor[Double, A]

    NB: These implicit defs are not mandatory but very helpful when playing with type classes ;-)…

    HTH

    • barnesjd says:

      Thanks! It makes sense, at least intuitively. I hope I can make time to try this out tonight.

  3. That’s the spirit! :)

    Your implicit conversion allows you to implicitly terminate the heterogenous list, that’s a nice trick, but unfortunately it does not work when pattern matching. Perhaps leaving that out and requiring explicit termination would not too big of a nuissance.

    If that’s acceptable, you could just rely on the shapeless HList, which works like that. It may already be known by some of your users. You could also look at KList (which I haven’t used). The doc says it is an heterogenous lists of types that share a common type constructor (like DataObject).

    Congrats for the new job’ !

    • barnesjd says:

      Thanks Patrick! I think you’ve made some good points yet again. I’ll take a second look at HList, and a first at KList. I think the latter is what I need. I initially abandoned HList because I didn’t see how I could parameterize the type to only allow a DataObject[Readable, _] vs a DataObject[Writable, _], etc. Perhaps with some of what I’ve learned from you and Andy will help me find my way.

    • barnesjd says:

      It looks promising, but I quickly hit the edge of my understanding of the type system yet again. :) I have sought the help of the community. FYI: https://groups.google.com/forum/#!topic/scala-user/TH9xP0xLzTY

Tagged with: scala (41), functional-programming (31), static-typing (16), snmp4s (3)