Scala: Abstract types vs generics

Solution 1:

You have a good point of view on this issue here:

The Purpose of Scala's Type System
A Conversation with Martin Odersky, Part III
by Bill Venners and Frank Sommers (May 18, 2009)

Update (October2009): what follows below has actually been illustrated in this new article by Bill Venners:
Abstract Type Members versus Generic Type Parameters in Scala (see summary at the end)

(Here is the relevant extract of the first interview, May 2009, emphasis mine)

General principle

There have always been two notions of abstraction:

• parameterization and
• abstract members.

In Java you also have both, but it depends on what you are abstracting over.
In Java you have abstract methods, but you can't pass a method as a parameter.
You don't have abstract fields, but you can pass a value as a parameter.
And similarly you don't have abstract type members, but you can specify a type as a parameter.
So in Java you also have all three of these, but there's a distinction about what abstraction principle you can use for what kinds of things. And you could argue that this distinction is fairly arbitrary.

The Scala Way

We decided to have the same construction principles for all three sorts of members.
So you can have abstract fields as well as value parameters.
You can pass methods (or "functions") as parameters, or you can abstract over them.
You can specify types as parameters, or you can abstract over them.
And what we get conceptually is that we can model one in terms of the other. At least in principle, we can express every sort of parameterization as a form of object-oriented abstraction. So in a sense you could say Scala is a more orthogonal and complete language.

Why?

What, in particular, abstract types buy you is a nice treatment for these covariance problems we talked about before.
One standard problem, which has been around for a long time, is the problem of animals and foods.
The puzzle was to have a class Animal with a method, eat, which eats some food.
The problem is if we subclass Animal and have a class such as Cow, then they would eat only Grass and not arbitrary food. A Cow couldn't eat a Fish, for instance.
What you want is to be able to say that a Cow has an eat method that eats only Grass and not other things.
Actually, you can't do that in Java because it turns out you can construct unsound situations, like the problem of assigning a Fruit to an Apple variable that I talked about earlier.

The answer is that you add an abstract type into the Animal class.
You say, my new Animal class has a type of SuitableFood, which I don't know.
So it's an abstract type. You don't give an implementation of the type. Then you have an eat method that eats only SuitableFood.
And then in the Cow class I would say, OK, I have a Cow, which extends class Animal, and for Cow type SuitableFood equals Grass.
So abstract types provide this notion of a type in a superclass that I don't know, which I then fill in later in subclasses with something I do know.

Same with parameterization?

Indeed you can. You could parameterize class Animal with the kind of food it eats.
But in practice, when you do that with many different things, it leads to an explosion of parameters, and usually, what's more, in bounds of parameters.
At the 1998 ECOOP, Kim Bruce, Phil Wadler, and I had a paper where we showed that as you increase the number of things you don't know, the typical program will grow quadratically.
So there are very good reasons not to do parameters, but to have these abstract members, because they don't give you this quadratic blow up.

thatismatt asks in the comments:

Do you think the following is a fair summary:

• Abstract Types are used in 'has-a' or 'uses-a' relationships (e.g. a Cow eats Grass)
• where as generics are usually 'of' relationships (e.g. List of Ints)

I am not sure the relationship is that different between using abstract types or generics. What is different is:

• how they are used, and
• how parameter bounds are managed.

To understand what Martin is speaking about when it comes to "explosion of parameters, and usually, what's more, in bounds of parameters", and its subsequent quadratically growth when abstract type are modeled using generics, you can consider the paper "Scalable Component Abstraction" written by... Martin Odersky, and Matthias Zenger for OOPSLA 2005, referenced in the publications of the project Palcom (finished in 2007).

Relevant extracts

Definition

Abstract type members provide a flexible way to abstract over concrete types of components.
Abstract types can hide information about internals of a component, similar to their use in SML signatures. In an object-oriented framework where classes can be extended by inheritance, they may also be used as a flexible means of parameterization (often called family polymorphism, see this weblog entry for instance, and the paper written by Eric Ernst).

(Note: Family polymorphism has been proposed for object-oriented languages as a solution to supporting reusable yet type-safe mutually recursive classes.
A key idea of family polymorphism is the notion of families, which are used to group mutually recursive classes)

bounded type abstraction

abstract class MaxCell extends AbsCell {
type T <: Ordered { type O = T }
def setMax(x: T) = if (get < x) set(x)
}

Here, the type declaration of T is constrained by an upper type bound which consists of a class name Ordered and a refinement { type O = T }.
The upper bound restricts the specializations of T in subclasses to those subtypes of Ordered for which the type member O of equals T.
Because of this constraint, the < method of class Ordered is guaranteed to be applicable to a receiver and an argument of type T.
The example shows that the bounded type member may itself appear as part of the bound.
(i.e. Scala supports F-bounded polymorphism)

(Note, from Peter Canning, William Cook, Walter Hill, Walter Olthoff paper:
Bounded quantification was introduced by Cardelli and Wegner as a means of typing functions that operate uniformly over all subtypes of a given type.
They defined a simple "object" model and used bounded quantification to type-check functions that make sense on all objects having a specified set of "attributes".
A more realistic presentation of object-oriented languages would allow objects that are elements of recursively-defined types.
In this context, bounded quantification no longer serves its intended purpose. It is easy to find functions that makes sense on all objects having a specified set of methods, but which cannot be typed in the Cardelli-Wegner system.
To provide a basis for typed polymorphic functions in object-oriented languages, we introduce F-bounded quantification)

Two faces of the same coins

There are two principal forms of abstraction in programming languages:

• parameterization and
• abstract members.

The first form is typical for functional languages, whereas the second form is typically used in object-oriented languages.

Traditionally, Java supports parameterization for values, and member abstraction for operations. The more recent Java 5.0 with generics supports parameterization also for types.

The arguments for including generics in Scala are two-fold:

• First, the encoding into abstract types is not that straightforward to do by hand. Besides the loss in conciseness, there is also the problem of accidental name conflicts between abstract type names that emulate type parameters.

• Second, generics and abstract types usually serve distinct roles in Scala programs.

  • Generics are typically used when one needs just type instantiation, whereas
  • abstract types are typically used when one needs to refer to the abstract type from client code.
    The latter arises in particular in two situations:
  • One might want to hide the exact definition of a type member from client code, to obtain a kind of encapsulation known from SML-style module systems.
  • Or one might want to override the type covariantly in subclasses to obtain family polymorphism.

In a system with bounded polymorphism, rewriting abstract type into generics might entail a quadratic expansion of type bounds.

Update October 2009

Abstract Type Members versus Generic Type Parameters in Scala (Bill Venners)

(emphasis mine)

My observation so far about abstract type members is that they are primarily a better choice than generic type parameters when:

• you want to let people mix in definitions of those types via traits.
• you think the explicit mention of the type member name when it is being defined will help code readability.

Example:

if you want to pass three different fixture objects into tests, you'll be able to do so, but you'll need to specify three types, one for each parameter. Thus had I taken the type parameter approach, your suite classes could have ended up looking like this:

// Type parameter version
class MySuite extends FixtureSuite3[StringBuilder, ListBuffer, Stack] with MyHandyFixture {
  // ...
}

Whereas with the type member approach it will look like this:

// Type member version
class MySuite extends FixtureSuite3 with MyHandyFixture {
  // ...
}

One other minor difference between abstract type members and generic type parameters is that when a generic type parameter is specified, readers of the code do not see the name of the type parameter. Thus were someone to see this line of code:

// Type parameter version
class MySuite extends FixtureSuite[StringBuilder] with StringBuilderFixture {
  // ...
}

They wouldn't know what the name of the type parameter specified as StringBuilder was without looking it up. Whereas the name of the type parameter is right there in the code in the abstract type member approach:

// Type member version
class MySuite extends FixtureSuite with StringBuilderFixture {
  type FixtureParam = StringBuilder
  // ...
}

In the latter case, readers of the code could see that StringBuilder is the "fixture parameter" type.
They still would need to figure out what "fixture parameter" meant, but they could at least get the name of the type without looking in the documentation.

Solution 2:

I had the same question when I was reading about Scala.

The advantage to using generics is that you are creating a family of types. Nobody will need to subclass Buffer—they can just use Buffer[Any], Buffer[String], etc.

If you use an abstract type, then people will be forced to create a subclass. People will need classes like AnyBuffer, StringBuffer, etc.

You need to decide which is better for your particular need.

Solution 3:

You may use abstract types in conjunction with type parameters to establish custom templates.

Let's assume you need to establish a pattern with three connected traits:

trait AA[B,C]
trait BB[C,A]
trait CC[A,B]

in the way that arguments mentioned in type parameters are AA,BB,CC itself respectfully

You may come with some kind of code:

trait AA[B<:BB[C,AA[B,C]],C<:CC[AA[B,C],B]]
trait BB[C<:CC[A,BB[C,A]],A<:AA[BB[C,A],C]]
trait CC[A<:AA[B,CC[A,B]],B<:BB[CC[A,B],A]]

which would not work in this simple way because of type parameter bonds. You need to made it covariant to inherit correctly

trait AA[+B<:BB[C,AA[B,C]],+C<:CC[AA[B,C],B]]
trait BB[+C<:CC[A,BB[C,A]],+A<:AA[BB[C,A],C]]
trait CC[+A<:AA[B,CC[A,B]],+B<:BB[CC[A,B],A]]

This one sample would compile but it sets strong requirements on variance rules and can not be used in some occasions

trait AA[+B<:BB[C,AA[B,C]],+C<:CC[AA[B,C],B]] {
  def forth(x:B):C
  def back(x:C):B
}
trait BB[+C<:CC[A,BB[C,A]],+A<:AA[BB[C,A],C]] {
  def forth(x:C):A
  def back(x:A):C
}
trait CC[+A<:AA[B,CC[A,B]],+B<:BB[CC[A,B],A]] {
  def forth(x:A):B
  def back(x:B):A
}

The compiler will object with bunch of variance check errors

In that case you may gather all type requirements in additional trait and parametrize other traits over it

//one trait to rule them all
trait OO[O <: OO[O]] { this : O =>
  type A <: AA[O]
  type B <: BB[O]
  type C <: CC[O]
}
trait AA[O <: OO[O]] { this : O#A =>
  type A = O#A
  type B = O#B
  type C = O#C
  def left(l:B):C
  def right(r:C):B = r.left(this)
  def join(l:B, r:C):A
  def double(l:B, r:C):A = this.join( l.join(r,this), r.join(this,l) )
}
trait BB[O <: OO[O]] { this : O#B =>
  type A = O#A
  type B = O#B
  type C = O#C
  def left(l:C):A
  def right(r:A):C = r.left(this)
  def join(l:C, r:A):B
  def double(l:C, r:A):B = this.join( l.join(r,this), r.join(this,l) )
}
trait CC[O <: OO[O]] { this : O#C =>
  type A = O#A
  type B = O#B
  type C = O#C
  def left(l:A):B
  def right(r:B):A = r.left(this)
  def join(l:A, r:B):C
  def double(l:A, r:B):C = this.join( l.join(r,this), r.join(this,l) )
}

Now we can write concrete representation for the described pattern, define left and join methods in all classes and get right and double for free

class ReprO extends OO[ReprO] {
  override type A = ReprA
  override type B = ReprB
  override type C = ReprC
}
case class ReprA(data : Int) extends AA[ReprO] {
  override def left(l:B):C = ReprC(data - l.data)
  override def join(l:B, r:C) = ReprA(l.data + r.data)
}
case class ReprB(data : Int) extends BB[ReprO] {
  override def left(l:C):A = ReprA(data - l.data)
  override def join(l:C, r:A):B = ReprB(l.data + r.data)
}
case class ReprC(data : Int) extends CC[ReprO] {
  override def left(l:A):B = ReprB(data - l.data)
  override def join(l:A, r:B):C = ReprC(l.data + r.data)
}

So, both abstract types and type parameters are used for creating abstractions. They both have weak and strong point. Abstract types are more specific and capable to describe any type structure but is verbose and require to explicit specified. Type parameters can create bunch of types instantly but gives you additional worry about inheritance and type bounds.

They give synergy to each other and can be used in conjunction for creating complex abstractions that can't be expressed with only one of them.