In a previous post I wrote about different interpolate methods in my program for linearly interpolating numbers and vectors. The methods for numbers and vectors are exactly the same, except for the types of the arguments and return value. So, ofcourse I wanted to write a generic interpolate method to avoid repeating myself.

For a type V to be useable by the interpolate method, it must satisfy two requirements:

1. It can be multiplied by a number, resulting in a V.
2. You can add two Vs together, resulting in a V.

I started with the idea to do this with a structural type (despite the performance disadvantage that structural types suffer from because methods are called via reflection – I just wanted to know if this could work in principle).

The requirements on the type can be described by a structural type directly, and then the interpolate method can be written in terms of the type V:

trait Container {
  type V = {
    def *(t: Double): V
    def +(v: V): V
  }

  def interpolate(t: Double, a: V, b: V): V = a * (1.0 - t) + b * t
}

That looks straightforward. But unfortunately, it doesn’t work…

<console>:8: error: recursive method + needs result type
           def +(v: V): V
                        ^
<console>:7: error: recursive method * needs result type
           def *(t: Double): V
                             ^

Note that the methods * and + in the type V refer to the type itself. Unfortunately, this is not allowed: structural types cannot be recursive, and that’s why you get these error messages. It’s impossible to use a structural type for the generic interpolate method.

On StackOverflow, oxbow_lakes put me on another track: you can do this with type classes. Type classes are an idea that comes from Haskell. The description on Wikipedia reads a bit academic and abstract, but the idea is really simple: a type class is simply a type that specifies some property of other types (it classifies types). Have a look at these two type classes, for example:

// A Multipliable is something that can be multiplied with a T, resulting in an R
trait Multipliable[-T, +R] { def *(value: T): R }

// An Addable is something that you can add a T to, resulting in an R
trait Addable[-T, +R] { def +(value: T): R }

These two can be combined into a type class Interpolatable, which satisfies the two requirements that are necessary for the interpolate method:

trait Interpolatable[T] extends Multipliable[Double, T] with Addable[T, T]

The interpolate method can now be written using this type class as follows:

def interpolate[T <% Interpolatable[T]](t: Double, a: T, b: T): T = a * (1.0 - t) + b * t

So, now we have a generic interpolate method that works on anything that can be viewed as an Interpolatable[T] (note the view bound, specified using <%). Ofcourse you now have to tell Scala that a type you want to use this with can indeed be viewed as an Interpolatable[T]; this can be done with an implicit conversion. For example for Double you can put the following implicit conversion somewhere so that it’s in scope:

implicit def doubleToInterpolatable(v1: Double) = new Interpolatable[Double] {
    def *(t: Double): Double = v1 * t
    def +(v2: Double): Double = v1 + v2
}

This all works great, but note that all in all we didn’t gain much with this approach. Although the interpolate method is generic, it’s still necessary to write an implicit conversion for each type that we want to use with the generic method – the repetition has simply shifted from the interpolate method itself to the implicit conversions that we have to write. In principle, though, the approach is valuable; interpolate is just a simple example. Suppose that you’d have a much larger and more complicated method than interpolate, then using this approach with type classes would really be worth it.

Here’s an interesting presentation by Daniel Spiewak in which he also talks about type classes.

A sidestep to C++

Note that in C++, using templates, it’s very easy to write a generic interpolate function that works on any type that satisfies the requirements, and you don’t need to specify this for each type that you want to use:

template <class T>
T interpolate(double t, T a, T b) {
    return a * (1.0 - t) + b * t;
}

There’s a big difference between templates in C++ and generics in Scala or Java. A template in C++ is used to generate code for some concrete type at the moment its necessary, and the compiler checks if the code generated from the template is valid (which it is if the concrete type satisfies the requirements). For example, if you use the template on doubles, the compiler generates an instance of the template specifically for double:

double interpolate(double t, double a, double b) {
    return a * (1.0 - t) + b * t;
}

In C++ there is no need to explicitly specify what the * and + functions do for the types that you want to interpolate; they automatically fall into place in the generated code.

Recently I ran into the following issue.

In one package object I have a method to linearly interpolate between numbers:

def interpolate(t: Double, a: Double, b: Double): Double = a * (1.0 - t) + b * t

And in another package object I have a method to linearly interpolate between vectors (where Vector is my own 3D vector class, which contains a * method to scale a vector with a number and a + method to add two vectors). It looks a lot like the method for numbers, but with different argument and return types:

def interpolate(t: Double, a: Vector, b: Vector): Vector = a * (1.0 - t) + b * t

I have another source file where I import both the package objects, so both interpolate methods are in scope. I’m trying to use one of the methods:

import org.jesperdj.scalaray._              // contains the interpolate method for numbers
import org.jesperdj.scalaray.vecmath._      // contains the interpolate method for vectors

val d: Double = interpolate(0.8, 1.5, 6.5)  // should call the first interpolate method

Unexpectedly, this doesn’t work – the Scala compiler (at least of version 2.8.0.RC7) gives you the following error message:

Example.scala:19: error: reference to interpolate is ambiguous;
it is imported twice in the same scope by
import org.jesperdj.scalaray.vecmath._
and import org.jesperdj.scalaray._
                val d: Double = interpolate(0.8, 1.5, 6.5)
                                ^
one error found

Very strange – the methods have different signatures, and I’m clearly calling the one with Double arguments, so there is really no ambiguity here. If I just define the two methods in the same scope, it works without a problem:

object Example {
  def interpolate(t: Double, a: Double, b: Double): Double = a * (1.0 - t) + b * t
  def interpolate(t: Double, a: Vector, b: Vector): Vector = a * (1.0 - t) + b * t

  def main(args: Array[String]) {
    // No problem!
    val d: Double = interpolate(0.8, 1.5, 6.5)
  }
}

I entered a ticket into the Scala bug tracking system, but it turns out I’m not the first one to discover this, there was already another ticket describing the same issue. Unfortunately, the Scala team decided that this will not be fixed, because it requires changes in the Scala specifications, which is a lot of work.

You can do something similar in Java, with import static. I tried it out and in Java it works without a problem:

import static example.Scope1.*;
import static example.Scope2.*;

public class Example {
    public static void main(String[] args) {
        // No problem!
        double d = interpolate(0.8, 1.5, 6.5);
    }
}

(where Scope1 and Scope2 are two classes that contain the two public static interpolate methods).

I came across this answer to a StackOverflow question by Mitch Blevins, about using the “Pimp My Library” pattern. Most Scala programmers will sooner or later discover this pattern. I’ve used it myself in my Scala ray tracer. I have a class Vector that represents a vector in 3D space. One of the methods it contains is a method to scale a vector uniformly with a factor:

final class Vector (val x: Double, val y: Double, val z: Double) {
        // ...
        
        // Scale a vector
        def *(f: Double) = new Vector(x * f, y * f, z * f)
}

So now I can write:

val a = new Vector(1.0, -1.0, 2.0)
val b = a * 1.5

// But I also want to be able to write this:
val c = 1.5 * a

Ofcourse, the Double type doesn’t have a * method that takes my class Vector as an argument. To make it work, I wrote an implicit method:

// Implicit conversion for scaling vectors by multiplying a numeric type with a vector
implicit def implicitScaleVector[N <% Double](f: N) = new {
        def *(v: Vector) = v * f
}

Note that the implicit method returns an “anonymous object” that contains the actual * method, which calls the * method defined in class Vector to do the work.

Ok, good, that works. But there’s an interesting problem with this implementation that Daniel Spiewak points out in a comment to Mitch’s answer: he says that the new { ... } syntax causes the compiler to infer a structural type, so that the * method inside the “anonymous object” will be called via reflection – which is much slower than a regular method call.

I wanted to see that for myself, so I wrote a small test program. Let’s first see how long the * method in class Vector takes to run:

class Vector (val x: Double, val y: Double, val z: Double) {
        def *(f: Double) = new Vector(x * f, y * f, z * f)
}

object Test {
        def time(block: => Unit) = {
                val start = java.lang.System.nanoTime()
                block
                val time = java.lang.System.nanoTime() - start
                println("time: " + time / 1e6 + " ms")
        }

        def main(args: Array[String]) {
                time {
                        var v = new Vector(1.0, -1.0, 2.0)
                        for (i <- 0 to 1000000) v = v * 1.5
                }
        }
}

I ran this a few times, it takes approximately 130 ms on my system. Now let's try the original version with the new { ... } syntax:

object Test {
        implicit def implicitScaleVector(f: Double) = new {
                def *(v: Vector) = v * f
        }

        // ...
        
        def main(args: Array[String]) {
                time {
                        var v = new Vector(1.0, -1.0, 2.0)
                        for (i <- 0 to 1000000) v = 1.5 * v
                }
        }
}

That is indeed a lot slower, on my system this takes about 280 ms, more than twice as slow! This performance problem can be solved by avoiding using a structural type:

object Test {
        class Result (f: Double) {
                def *(v: Vector) = v * f
        }

        implicit def implicitScaleVector(f: Double) = new Result(f)

        // ...
}

This indeed performs much better, it takes only about 140 ms - almost as fast as calling the * in class Vector directly.

There is one thing I don't like about this however, and that's that I need an additional class that's polluting the namespace. I tried to fix this by declaring the class inside the method:

object Test {
        implicit def implicitScaleVector(f: Double) = {
                class Result (f: Double) {
                        def *(v: Vector) = v * f
                }

                new Result(f)
        }

        // ...
}

Unfortunately that doesn't work! This is just as slow (280 ms) as the original version with the new { ... } syntax. That's because class Result is now not known to the caller of the implicit method, so that it still needs to infer the structural type and call the method via reflection.

This is an interesting gotcha to be aware of when pimping libraries or using structural types in other ways.

While working on a Scala hobby project, I wanted to convert an Option[A] into an Option[B]. I’ve noticed that it’s often straightforward to come up with an ugly way to do things in Scala, but with a little more thought it’s almost always possible to find a much more elegant and concise way to do things. I had initially written the following:

def intersect(ray: Ray): Option[Intersection] = {
  val opt = shape intersect ray    // Returns an Option[(DifferentialGeometry, Double)]
  if (opt.isEmpty) None else {
    val (dg, t) = opt.get
    Some(new Intersection(dg, t, this))
  }
}

This code is part of my Scala ray tracer (which isn’t yet publicly available – at the moment it’s too incomplete). It calls the intersect method on a shape, which returns an Option containing two values: a DifferentialGeometry object that contains information about the intersection point on the surface of the shape, and a Double which is the distance of the intersection point along the ray.

The intersect method above is part of class Primitive, which represents an object in the scene – something that has a shape, a material and other properties. This method converts the Option[(DifferentialGeometry, Double)] into an Option[Intersection] – class Intersection represents an intersection between a primitive and a ray.

I wasn’t satisfied with the code above, and after looking at the Scala API documentation I discovered that it can be written much more concisely by using the collect method of class Option, like this:

def intersect(ray: Ray): Option[Intersection] =
  shape intersect ray collect { case (dg, t) => new Intersection(dg, t, this) }

The collect method takes a partial function as an argument. It returns None for inputs for which the partial function isn’t defined, and a Some(...) for inputs for which the partial function is defined. The partial function can be written as { case value => ... }. By writing the code this way, I don’t have to deal with checking, unpacking and packing the Option objects myself, which makes the code nice and clean.

edit: Using map instead of collect is a little bit more efficient, as Brian Howard points out. See the comments for details.