Does scala provide anything like C++ templates?

Question

I'm coming from C++ and trying to wrap my head around scala's type system.

Consider the following C++ template class:

template<class T>
class Point2
{
  Point2( T x, T y ) :
     x(x),
     y(y)
  {}

  T x;
  T y;
  Point2<T> operator+( Point<T> const& other ) const
  {
     return Point<T>(x+other.x, y+other.y);
  }
  T sumComponents() const { return x+y; }
}

Point2<Double> p0(12.3, 45.6) 
Point2<Double> p1(12.3, 45.6) 
Point2<Double> p = p1+p2
Double d = p1.sumComponents()

I'm finding I want to write something like this:

case class Point2[ T ] (x:T, y:T) {
   def +() Point2[T]: = x+y
   def sumComponents() T: = x+y
}

or, (because the compile has problems with this),

trait Addable[T] {   // Require T supports the + operatory
   def +( that:T ):T
}
case class Point2[ T<:Addable[T] ] (x:T, y:T) {
   def +() Point2[T]: = x+y
   def sumComponents() T: = x+y
}

which is similarly problematic because I can't require Double to extend Addable.

Generally, I'm finding it scala's type system works with a set of constraints that I don't quite understand.

What's the idiomatic way of implementing the above in scala?

And what's the right way for C++ template programmers to understand the limits of generics in scala? (why can't I do this in scala? e.g. Is it because generics are compiled before being instaniated?)

Answer 1

What's the idiomatic way of implementing the above in scala?

Either by specifying appropriate requirements of T, or using type classes to provide the desired behavior. I'll get back to this later.

And what's the right way for C++ template programmers to understand the limits of generics in scala? (why can't I do this in scala? e.g. Is it because generics are compiled before being instaniated?)

C++ templates are compiled "at" the usage site, and different code is generated for each combination of parameters to the templates. So if you use the class above with int and double, you get two different Point2 classes compiled.

Basically, C++ templates are macros, though nowhere near as dumb as #define macros. In fact, C++ templates are turing complete. Maybe it will be possible to accomplish something equivalent in the future, with the upcoming macro capabilities planned for Scala 2.11 and beyond, but let's ignore that for now.

Type parameters (Scala equivalent of Java generics) do not change how a code is compiled. A parameterized class generates its bytecode when it is compiled, not when it is used. So, by the time one instantiates a Point2 with Double, it is too late to generate bytecode.

That means that the code generated by a parameterized class must be compatible with all types a class can be instantiated with.

And that's the source of the trouble: any methods called on T must be known to be present on T at the time Point2 is compiled. Therefore, T must be defined to have an upper boundary of traits or classes that define such methods, as you have shown in your example.

Of course, that is not always possible, as you rightly pointed out, and that's where type classes come in. A type class is a set of types for which a set of behaviors is defined. Type classes, as implemented in Scala, are defined as classes whose instances define the behavior of other classes.

In the example you gave, you'd be using either the Numeric type class, or the Fractional type class if you need fractional division as well. A simple example of type class use is:

scala> import scala.math.Numeric
import scala.math.Numeric

scala> def sum[T](x: T, y: T)(implicit num: Numeric[T]): T = num.plus(x, y)
sum: [T](x: T, y: T)(implicit num: scala.math.Numeric[T])T

Or, using a special notation called "context bounds",

scala> def sum[T : Numeric](x: T, y: T): T = implicitly[Numeric[T]].plus(x, y)
sum: [T](x: T, y: T)(implicit evidence$1: scala.math.Numeric[T])T

The notation T : Numeric can be read as T such that there's an implicit instance of Numeric[T] available. The code implicitly[X] returns an implicit value of type X if one can be found (or fails at compile time).

Now, notice how no method is called on x and y -- instead, we call methods on num whose class is Numeric[T]. The class Numeric[T] has a method plus which knows how to add two Ts.

Because what we need is type class instances, one can easily add new types to satisfy a type class. One could easily declare a Numeric type class for Point2 (assuming all its methods could be implemented):

class Point2Numeric[T](implicit num: Numeric[T]) extends Numeric[Point2[T]] {
  def plus(x: Point2[T], y: Point2[T]): Point2[T] = x + y
  // etc
}
implicit def ToPoint2Numeric[T : Numeric] = new Point2Numeric[T]

With that in place, then for any T for which there's a Numeric[T], there would be also a Numeric[Point2[T]].

After plain type inheritance (upper type bounds), type classes are the most common form of type constraint used in Scala. There are other forms a bit more sophisticated, for which there's some discussion whether they are type classes or something different -- the magnet pattern, for instance. Look at shapeless for an example of how far one can take such things.

Another kind of type constraint that used to be very common but is now being used more circumspectly are view bounds. I'll not go into details (in fact, search for context bounds and view bounds to find a long answer about it from myself), but they can be used to make type classes more readable when used. For example:

scala> import scala.math.Numeric.Implicits._
import scala.math.Numeric.Implicits._

scala> def sum[T : Numeric](x: T, y: T): T = x + y
sum: [T](x: T, y: T)(implicit evidence$1: scala.math.Numeric[T])T

The imported definitions contain implicit conversions that make it possible to use values of type T for which there's a Numeric[T] as if they, themselves, had the methods like + or -.

As a final note, it is important to realize this goes through many levels of indirection and, therefore, might not be very suitable for high performance code.