This page is no longer maintained — Please continue to the home page at www.scala-lang.org

# Multimethod-ing the builder pattern, or how to fight Scalala bitrot with types

2 replies
David Hall 4
Joined: 2009-08-21,

Hi,

Sorry about the long email. Basic idea: if you were to add a method to
the collection hierarchy called

foo[Coll,Ret](x: Coll)(implicit magic: Magic_![List,Coll,Ret]):Ret

whose return type depended on *both* sets of arguments, how would you
handle the multiple dispatch?

After talking to Matthew Pocock in his travails with understanding the
morass of type classes and implicits in Scalala, I decided it's
probably time to simplify them. (Various reasons: it's hard to follow
all the logic for both the programmer and the compiler, the build
times are long, specialization gets confused, etc.)

Scalala is a linear algebra package, and its current class hierarchy
is heavily influenced by the collections library. For instance,
there's a TensorLike[KeyType,ValueType,TensorType] trait and there's
Tensor[KeyType,ValueType] <: TensorLike[KeyType, ValueType,
Tensor[KeyType,ValueType]. Then, Vector[ValueType] would inherit from
Tensor[Int,ValueType] with
TensorLike[Int,ValueType,Vector[ValueType]]. This works wonderfully
for getting things like map right. The problem arises with the binary
operators:

trait TensorLike[KeyType,ValueType,TensorType] {
// ... simplified, somewhat
def +[Other, Ret](that: Other)(implicit op:
BinaryOp[TensorType,Other,OpAdd,Ret]) = op(self,that)
}

So all that's required is a BinaryOp instance for any operation type
you want to support. This works well when all types are fully
statically resolved. It's easy to do something like:

DenseVector + SparseVector -> DenseVector
SparseVector + SparseVector -> SparseVector
SparseVector + DenseVector -> DenseVector

by just specifying a lot of type class instantiations.

The problem is what to do when types aren't fully known at compile
time. Ideally, we'd like:

(dv: Vector) + (sv: Vector) -> Vector, but dynamic type should be DenseVector.

Note that this is analogous to how (list: Iterable[Int]).map( ...) works.

This is a classic multimethod kind of thing, but put into the type
class/builder pattern world that seems like it's becoming best
practice in Scala land. I don't know how to do this correctly. At the
moment, there are a lot of casts and other horrible things that live
on the LHS of the operator, but it doesn't really seem extensible in
the same way that you get with single-dispatch.

Thoughts?

Thanks,
David Hall

Ben Hutchison 3
Joined: 2009-11-02,
Re: Multimethod-ing the builder pattern, or how to fight Scalal

On Wed, Sep 14, 2011 at 3:30 PM, David Hall wrote:
> The problem is what to do when types aren't fully known at compile
> time. Ideally, we'd like:
>
> (dv: Vector) + (sv: Vector) -> Vector, but dynamic type should be DenseVector.
>
> Note that this is analogous to how (list: Iterable[Int]).map( ...) works.

For your particular example, asking the left hand Vector "dv" for a
result "DenseBuilder" seems to be enough to get a Dense result, as
scala collections do? The trick would be if you wanted eg this to
happen as well:

(sv: Vector) + (dv: Vector) -> DenseVector

Alternately, to switch between denseness/sparsity in particular, you
could use a heuristic in the result Builder. Presumably, you can give
it a sizeHint upfront? Thereafter, track the proportion of non-empty
cells in the Vector afterwards and allocate the result vector
suitably.

Its an interesting grey area -the tension between asymmetric OO and
typeclasses, and static vs dynamic types. I don't know what design I
believe is "right". I'd be interested to hear of any other troublesome
cases you encounter other than the sparsity example?

-Ben

David Hall 4
Joined: 2009-08-21,
Re: Multimethod-ing the builder pattern, or how to fight Scalal

On Wed, Sep 14, 2011 at 4:28 PM, Ben Hutchison wrote:
> On Wed, Sep 14, 2011 at 3:30 PM, David Hall wrote:
>> The problem is what to do when types aren't fully known at compile
>> time. Ideally, we'd like:
>>
>> (dv: Vector) + (sv: Vector) -> Vector, but dynamic type should be DenseVector.
>>
>> Note that this is analogous to how (list: Iterable[Int]).map( ...) works.
>
> For your particular example, asking the left hand Vector "dv" for a
> result "DenseBuilder" seems to be enough to get a Dense result, as
> scala collections do? The trick would be if you wanted eg this to
> happen as well:
>
> (sv: Vector) + (dv: Vector) -> DenseVector

Right, we definitely want this (at least the DV dynamic type)

>
> Alternately, to switch between denseness/sparsity in particular, you
> could use a heuristic in the result Builder. Presumably, you can give
> it a sizeHint upfront? Thereafter, track the proportion of non-empty
> cells in the Vector afterwards and allocate the result vector
> suitably.

Hrm, good idea. The problem is that we'd like the library to be
somewhat extensible too. Maybe this is too much, but for instance
ideally we'd like:

(dv: Vector) :* (sv: Vector) -> SparseVector
(dv: Vector) :* (sparseVectorWithHashStorage: Vector) -> SparseHashVector
(dv: Vector) * (sparseMatrix: Matrix) -> appropriate kind of sparse vector

(:* is element-wise product), where maybe the user defines some
speciality SparseMatrix, since there seems to be dozens of
implementations.

>
> Its an interesting grey area -the tension between asymmetric OO and
> typeclasses, and static vs dynamic types. I don't know what design I
> believe is "right". I'd be interested to hear of any other troublesome
> cases you encounter other than the sparsity example?

Yeah, precisely. The Collections lib walks a really impressive tight
line that gets most everything right with a surprising amount of
elegance, but it's not immediately clear if it scales to multimethods
in the same way. It might be that we have to resort to some kind of
dynamic registry to get the dynamic types right. Not ideal, but it
seems like almost all multimethod layers end up resorting to that at
some point.

Thanks!

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland