Operators

Operators in Scalala

One design goal of Scalala is to elegantly express mathematical operators on arbitrary collections of heterogeneous numeric types, whether or not they are part of scalala's tensor type hierarchy.

Scalala supports this out of the box, with the correct static return types. Currently, there is full support for Arrays, Sequences, Maps, and tuples (up length 3 or less). The goal is that if you add together two such collections, you'd expect the answer to be a similarly-typed collection consisting of the sum of the corresponding collection elements.

But first a bit of a digression. It's clear that when you add two Ints, you expect the answer to still be an Int. Scala, like most modern languages, allows + to sit between numeric arguments with different primitive types. So + is a heterogenous numeric operator, and it returns the type of the more flexible numeric argument.

scala> 1 + 2.0
res0: Double = 3.0

Great. We want this kind of flexibility for collections of numeric arguments, but from a library that has no explicit help from the compiler, runtime, etc. Fortunately, scala is flexible enough to support this somewhat gracefully.

Let's take a look at some examples of pairwise multiplication.

import scalala.operators.Implicits._
import scalala.collection.sparse.SparseArray

scala> Array(1,2,3) :* Array(2,2,2)
res3: Array[Int] = Array(2, 4, 6)

scala> Array(1,2,3) :* Array(2.0,2.0,2.0)
res2: Array[Double] = Array(2.0, 4.0, 6.0)

Statically, the returned value is an Array of either Int or Double (or other types, etc), depending on the type arguments to the operands. What about heterogeneous collection types?

scala> SparseArray(1,0,2) :* Array(2.0,2.0,2.0)
res3: SparseArray[Double](2.0,0.0,4.0) **

scala> SparseArray(1,0,2) :+ Array(2,2,2)
res4: Array[Int](3,2,4) **

The type of the collection itself can depend on the operator being used. A SparseArray times an Array should itself be sparse, whereas the sum of these same two arguments should be a (dense) Array.

[** I've taken some liberties with fake pretty-printing ]

How it works

There are two components to making this work: first, implicit promotions from collection types to rich collection types (such as RichArray) that define methods like :* (for pairwise multiplication), as well as :+ :- :/ :^ and :%. (And, for mutable collection types, there are mutating variants as well, :+= :-= :*= :/= :^= :%=.)

 def :*[B,That](b : B)(implicit op : BinaryOp[This,B,OpMul,That]) : That = op(repr,b);

This method, as called in our example lines above, expects an argument of type B and an implicit argument of type BinaryOp[This,B,OpMul,That]. ("This" is the static type of the enclosing class.) The return type of the whole expression is That. The compiler will insert an appropriate instance of BinaryOp depending on the the type of the left and right arguments to :*, and the return value will be whatever has been specified as the fourth type argument to BinaryOp in the instance the compiler finds.

In this way, BinaryOp is a builder trait for numeric operators that tells the "rich" wrapper object how to do actually perform the multiplication.

/** Operation that creates That from A and B. */
trait BinaryOp[@specialized -A, @specialized -B, Op<:OpType, +That] {
 def apply(a : A, b : B) : That;
}

/** Construction delegate for A :* B. */
trait OpMul extends OpType;

The companion object for BinaryOp defines implicit objects and implicit methods that provide behavior for many things that might be multiplied. For instance, there are definitions for primitives (BinaryOp[Int,Int,OpMul,Int], BinaryOp[Int,Double,OpMul,Double] BinaryOp[Double,Int,OpMul,Double], etc). Similarly, the companion object provides implicit objects and implicit methods for creating collection-level multiplication instances. For example, the compiler can find an instance of BinaryOp[Array[A],Array[B],O,Array[RV]] if it can find an implicit instance of BinaryOp[A,B,O,RV] for any op type O. It can also find Binaryop[Array[A],B,O,Array[RV]] to support things like:

scala> Array(1,2,3) :* 4
res6: Array[Int] = Array(4, 8, 12)

More implementations, supporting more collection types, can be added and optimized appropriately. New scalar types (such as complex numbers) can be implemented, too, and will carry through so that all collection-level operations will work with them automatically. And library designers who wish to override the default implementations can simply import new BinaryOp instances to override the default and provide new behavior within a code block.

In the Scalala code, there are more detail needed to get this exactly right, such as limiting scope to certain shapes (such as only matching some arguments to scalars), supporting shaped (e.g. matrix-level) operations in addition to pairwise, etc.

I hope I've made the basic intuition clear. Scala's rules for implicits allow operators to be implemented via builder traits, and the most appropriate trait is found or constructed at the site an operator is used. It's all type-safe, known statically at compile time, pretty flexible, and (hopefully) reasonably fast.