Wednesday, May 18, 2011

Making the most of Scala's (extremely limited) type inference

The lack of good inference is one of the most annoying things hindering Scala's usability as a functional language, and it's actually been a real problem for us in some of the code we write at Capital IQ. Good type inference is important for functional programming - it is important to be able to pull any common functionality out into higher-order functions, and not be penalized with a boatload of manual type annotations for doing so. I liken the friction we sometimes encounter dealing with Scala's poor type inference to be something like what one would encounter doing functional programming in Java - yes, you can use anonymous classes to simulate first-class functions, etc, but the amount of boilerplate really discourages you.

With all that said, there are some workarounds and rules you can follow to make the most of Scala's limited inference. Type information in Scala flows from function arguments to their results (when the types of a function's arguments are known, that type information will flow into the body of the function), from left to right across argument lists, and from first to last across statements. This is in contrast to a language with full type inference, where (roughly speaking) type information flows unrestricted in all directions. But, if you pay attention to Scala's limitations, you can get better type inference out of your APIs. (Scala will also never infer a higher-kinded type which is a partially applied type-level function, but that is a topic for another post.)

Let's look at a first example, illustrating the fact that type information does not flow from a function's body to its arguments:
scala> case class Foo() { def quuux(f: Foo) = 12 }
defined class Foo

scala> val f = (x,y) => x quuux y
error: missing parameter type
val f = (x,y) => x quuux y
         ^
error: missing parameter type
val f = (x,y) => x quuux y
           ^
So, even though the body of the lambda fixes the types of x and y to be Foo (no other class in scope has a method quuux), this type information will not flow 'upwards' to the function's arguments. This is a good thing to keep in mind as you are designing your APIs. Epecially when writing higher-order functions, you often expect to receive anonymous functions whose types you'd like inferred.

Here's an example:
def zipWith[A,B,C](a: List[A], b: List[B], f: (A,B) => C): 
  List[C] = a zip b map f.tupled
Note what happens when we try using this function:
scala> zipWith(List(1,2), List(2,3), (a,b) => a+b)

error: missing parameter type
zipWith(List(1,2), List(2,3), (a,b) => a+b)
                               ^
error: missing parameter type
zipWith(List(1,2), List(2,3), (a,b) => a+b)
                                 ^
What's going on here? Type information does not flow from left to right within an argument list, only from left to right across argument lists. So, even though Scala knows the types of the first two arguments, which would fix the type parameters A and B to be Int, that information does not flow to our anonymous function.

If we change our definition of zipWith to be curried, then we can get type information to flow from the arguments to our binary function:
scala> def zipWith[A,B,C](a: List[A], b: List[B])(f: (A,B) => C):
  List[C] = a zip b map f.tupled

zipWith: [A,B,C](a: List[A],b: List[B])(f: (A, B) => C)List[C]

scala> zipWith(List(1,2), List(2,3))((a,b) => a+b) 
res1: List[Int] = List(3, 5)

scala> zipWith(List(1,2), List(2,3))(_ + _)
res2: List[Int] = List(3, 5)
Now that our binary function is in a separate argument list, any type information from the previous argument lists is used to fill in the types for our function. So, A and B are fixed to be Int by the first argument list, and therefore we don't need to annotate our lambda's parameters. From here, the type information about our lambda's function parameters will flow into the body of the lambda, and in this case, following the same inference rules, Scala is able to infer the result type - in this case, again, Int. Note that if you have a method bar on some object foo, the type inference flow for foo.bar(x,y) is going to be the same as if you defined bar as a standalone function def bar (foo: Foo)(x: X, y: Y). This explains why our actual implementation of this function - a zip b map f.tupled - does not require type annotation.

Incidentally, this restriction that type information does not flow at least left to right within a single argument list appears completely artificial to me. I posted a ticket about this a while ago - Jason Zaugg commented there about the trick of currying the arguments to get better type propagation.

Question: do you think the following will require type annotations?
scala> zipWith(List(List(1,2)), List(List(2,3)))(
  zipWith(_,_)(_ + _))
The answer is... no! But why? Expanding this out a bit, we have:
scala> zipWith(List(List(1,2)), List(List(2,3)))(
  (a,b) => zipWith(a,b)(_ + _))
By the previous reasoning, the types of a and b will be known (fixed from the previous argument list). Now we apply the rule that type information flows from a function's arguments into its body. From this Scala infers the type A and B for the inner zipWith, and as a result the argument types for (_ + _) are known. This information flows into the body of (_ + _), and Scala is able to infer the result is Int.

Note that if we were to declare our lambda outside of the call to zipWith, we don't get good type inference flow since type information does not flow backwards across statements - only forwards:
 scala> {val f = (_ + _); zipWith(List(1,2), List(2,3))(f)}
error: missing parameter type for 
expanded function ((x$1, x$2) => x$1.$plus(x$2))
{val f = (_ + _); zipWith(List(1,2), List(2,3))(f)}
          ^
error: missing parameter type for 
expanded function ((x$1 , x$2) => x$1.$plus(x$2))
{val f = (_ + _); zipWith(List(1,2), List(2,3))(f)}
              ^
So, it's actually better for type inference to not declare variables for expressions you are only going to reference once. This is the style I prefer anyway, and it's much more common in purely functional programming - you just get used to reading more nested expressions, and the structure of the code is more clear.

Judicious use of these rules can make your APIs much more usable. But don't overdo it - for instance, writing zipWith like this does not improve type inference over our previous version:
def zipWith[A,B,C](a: List[A])(b: List[B])(f: (A,B) => C): 
List[C]
There is no type information to flow from the first argument list to the second - the types A and B are completely unrelated. So we might as well put a and b in the same argument list.

Scala's limitations are particularly unfortunate - as we've seen, in many cases the information is there to do better inference and the restrictions in place are artificial. I really hope the Scala developers put some more resources into improving the type inference in Scala - it's one of those improvements that isn't an obvious 'feature' win but it can dramatically improve everyday work in Scala for those who are using the language heavily.

17 comments:

Daniel Spiewak said...

Unfortunately, Scala's type inference is very nearly as good as it can get. Anything more and we jump the rails into constraint typing, which is not going to work. Even fixing the issue with a single parameter list requires unification. And while I don't think it would be particularly unsound in that case, I may not be seeing all of the permutations.

The reason constraint typing is a problem for Scala is in the nominal type equality combined with record types. Constraint typing yields a structural type for any object. While Scala has a form of structural typing built into the language, it is far too weak to do anything useful (e.g. open recursion is out, which basically means it's not OO but simply record types). Adding more powerful structural typing would be a major overhaul to the type system and would severely hamper other design goals like Java interop and performance (the JVM is pretty heavily biased toward nominal typing).

On the other extreme, it is *possible* to do constraint typing in a nominal type system with subtyping, but you have to give up entirely on separate compilation. Type checking effectively turns into a special case of control-flow analysis, which not only makes the whole process exponential, but also completely kills the idea of reusable APIs and separately distributable libraries, since the entire program must be available to the type checker in order to definitively derive the union type at a particular declaration site.

Given the limits of statically typed OO in a nominal type system, I think Scala's inference is pretty impressive! The trick with parameter unification from left-to-right across parameter sets is very, very useful, and (as you point out) cuts down on the number of requisite type annotations by a large degree. Do I long for a more powerful system? Yes, but that system would be incompatible with the Scala we know today.

martin said...

Daniel is correct theoretically but wrong practically. Structural subtyping does lead to simpler and more tractable constraint systems but the size of constraints blows up to a degree where typically the size of a type is proportional to the size of the expression in which it occurs (with a large constant factor). There is no practical language out there which combines subtyping, type-inference, and structural types and for good reason. We tried that with Funnel before Scala. It's just not usable.

Paul Chiusano said...

@Daniel - I think you are talking about something different. I wouldn't mind so much being forced to annotate the types of values and functions at module boundaries. I am just asking that Scala do better local inference, using the information it already has available - this would be a huge improvement over the current state. Why would this require giving up on separate compilation?

martin said...

The problem is not so much nominal typing as subtyping. There are lots of papers that combine subtyping with Hindley-Milner (some of them written by me), but we have found that it does not work in practice. Constraints get too big, error messages get too messy.

Paul Chiusano said...

@martin - Can you comment on the feasibility of improving local type inference by letting type information flow more bidirectionally, as I suggest? I am sure there are some caveats, but is there anything really fundamental here? And how likely is any of this to happen in a future Scala release?

martin said...

@paul We know very little about what can be done. You need something which can be specified (i.e. not simply a compiler hack) and that is algorithmically tractable. Progress here looks very hard. So I can't speculate whether it will be made at some point and whether Scala will adopt it.

Paul Chiusano said...

@martin - Interesting. Thanks for your response. It does seem though like there is some low-hanging fruit though that doesn't require any breakthroughs.

But regardless of how easy this is, I really do hope that there's some emphasis placed on better type inference for Scala going forward. It really would be a huge improvement in usability!

Btw, I think part of the reason not many people complain about this in the Scala community is that many people in the Scala community are coming from languages with no type inference, and for them Scala is definitely a vast improvement! But for those of us coming from languages like Haskell with more complete inference, and with firsthand experience of how much this improves usability when doing FP, Scala's limitations are more of an issue.

Daniel Spiewak said...

@Martin

I agree that constraint based structural subtyping balloons types extensively. However, I remain unconvinced that the problem is entirely intractable. It seems to me this is a tooling issue, and tools improve with time and research. Merging constraint typing with *nominal* subtyping, on the other hand, is theoretically dubious and will always remain so. No amount of research is going to help us in that department.

Re: "not so much nominal typing as subtyping". I would argue that is an artificial distinction. You can't really say "subtyping" with out defining the method by which you relate types, and that method is going to be either structural or nominal. Obviously, nominal typing *without* subtyping is no problem for constraint typing, as evidenced by SML.

@Paul

It's really hard to say "annotating at module boundaries", since module boundaries are theoretically artificial. That's the whole point of having a language made up of composable, orthogonal concepts! Methods are really just named function values, class bodies are constructor bodies, even side-effecting expressions are merely just unassigned values. Everything is a "let".

Scala could *conceivably* make val in a particular method scope magical. So, constraint sets are built for local vals, but not across function boundaries. Unfortunately, that would end up being too restrictive, since you would miss out on very useful cases like this:

xs.foldLeft(Nil) { _ :: _ }

Without building constraints across function boundaries, then the above will still produce an error due to over-specificity. However, if we *do* build constraints across function boundaries, then we start expanding the problem into intractable territory once again.

One thing we could do is make top-level methods (i.e. class members) magical, and say that we'll infer everything *inside* those methods in a single unification. That *might* work, but it still seems to me like you could tie yourself in knots with inner functions (anonymous or otherwise).

As Martin said, this isn't a simple matter. It would really be nice if we had a Featherweight Scala so that we could try out some of these ideas in a more tractable setting, but obviously that effort hasn't been an easy (or fruitful) road thus far.

Summary: type checking Scala is hard. Really, really, really hard.

Paul Chiusano said...

@Adriaan - I got an email with your comment but it seemed to enter a black hole and never got posted. Here is Adrian Moors comment -

----

Actually, scalac has merrily been inferring type constructors (though extremely limited[*]) since 2.8 (svn revision r19245, git commit d56def).

[*] where "extremely limited" is defined as "restricted to first-order unification. Higher-order unification is feasible, but needs research before it can be implemented.

ps: in most cases it's more accurate to use "type constructor" than "higher-kinded type" -- it's also less scary

----

@Adriaan - yes I was specifically talking about inferring partially applied type constructors. Unary type constructor inference seems to work. But Scala will not infer a type constructor like Map[K,_] or State[S,_].

Alex Iliev said...

Late comment...I just saw this post on Planet Scala.

An unfortunate side-effect of this approach to optimizing type inference is that curried parameters get declared in an order which is bad for partial application.

Often you want the function parameter to be the first one, so that you can apply your HOF partially. That's why the likes of foldX in Haskell take the function as a first parameter. But in Scala it's the second one.

Cheers
alex

Daniel Spiewak said...

@Alex

The fact that Scala does its parameters in the "wrong" order (most-specific to least-specific) is not just a product of its type inference, but also a product of its nature as an object oriented language. Fold is a fantastic example.

In Haskell:

foldl :: (a -> b -> a) -> a -> [b] -> a

In Scala:

[A, B]A => (A, B) => A => A

But, remember that there is a "hidden" first argument that is the dispatch receiver:

[A, B]List[A] => A => (A, B) => A => A

So, *precisely* the opposite of Haskell, and unavoidably so. That "hidden" first argument will always be the most specific parameter in a dispatch, because that's how OO works. If you tried to do it the other way, you would have foldLeft being a method on Function2, which would be weird.

In short, point-free dispatch is nearly impossible to consistently achieve in Scala primarily because of object-orientation. Type inference is a secondary limiter.

Daniel Spiewak said...

(note: my type signature is wrong for foldLeft, stemming from the fact that Scala doesn't give you a super-nice way to get those sorts of types and I had to do a lot of manual editing. Sorry!)

Zoheb said...

I just ran into this issue. I was wondering, why this is fundamentally hard.

Why can't the compiler try out all n! permutations (possibly only for n <= 5) of argument orders and see if type inference succeeds for any of them using the current algorithm. This is exponential but function argument lists are typically small in size.

Anonymous said...

A common pattern for working around Scala's inability (or unwillingness) to infer types left-to-right across argument lists seems be just currying the function or method definition since Scala will infer across applications. Why couldn't the compiler just try assigning types assuming the arguments were fully curried if the normal typing fails? It might not be as powerful as it could be, but it would cover many practical cases. (Adding those types is painful and ugly to boot)

Paul Chiusano said...

I have never gotten a good answer as to why something seemingly simple like what you or Zoheb suggests would be impossible. Maybe it is kind of a hack, but so what? It would improve usability of the language in a large number of cases.

carlos said...

this line is killing me: "type information does not flow from left to right within an argument list, only from left to right across argument lists."

I've read it several times and I can't found the difference in the context between "within" and "across" (could be because I'm not a native english speaker?)

can you explain a bit more this difference?..thanks!!

Tikhon Jelvis said...

@carlos: Type information does not flow inside a single parameter list in a single function call:

f(a, b, c)

In this example, the types of a, b and c cannot influence each other.

However, if you curry the function and break it out into two function calls with separate parameter lists, type information can flow from the first to the second:

f(a, b)(c)

In this example, information from a and b can influence c.