Scala: Abstract types vs generics

Question

I was reading A Tour of Scala: Abstract Types. When is it better to use abstract types?

For example,

abstract class Buffer {
  type T
  val element: T
}

rather that generics, for example,

abstract class Buffer[T] {
  val element: T
}

Anticathode

Answer 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.

Foxe

How am I supposed to get karma points by answering Scala questions when you come and do this??? :-) – Engorge

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) – Anticathode

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. More in my answer in a moment. – Foxe

Note to self: see also this May 2010 blog post: daily-scala.blogspot.com/2010/05/… – Foxe

F-bounded polymorphism appears to work with type parameters also, e.g. trait C[T <: Ordered[T]]. And dependent method types mentioned for family polymorphism can also be done with type parameters. Appears only the quadratic explosion of type bounds point remains. See also. – Necrophilism

I would like to narrow this question down a bit: Is there anything that I can do with type parameters that I can not do with abstract type members? – Oddson

We decided to have the same construction principles for all three sorts of members. abstract class A { def a[T](t: T): T } How do I abstract over the method a with parameterization? – Redroot

@PaulDraper That would be best as its own question (with a link back to this one for context) – Foxe

Answer 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.

Poilu

mmm thins improved a lot on this front, you can just require Buffer { type T <: String } or Buffer { type T = String } depending on your needs – Beaver

Answer 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.

Kristynkrock

We can add type parameters to the methods and save compilation for type-parameter case: def forth[B1 >: B](x: B1): C, def back[C1 >: C](x: C1): B etc. – Bartram

Answer 4

Stephen Compall. Type members are (almost) type parameters https://typelevel.org/blog/2015/07/13/type-members-parameters.html

Jon Pretty @propensive. Type Members vs Type Parameters - NE Scala 2016 https://www.youtube.com/watch?v=R8GksuRw3VI

Type parameters can be made type members

trait A[_T] {
  type T = _T
}

Type members can be made type parameters

trait A { type T }
object A {
  type Aux[_T] = A { type T = _T }
}

// using A.Aux[T] instead of A[T]

But:

• Type members can't be used in primary constructor and self-type { self: T => .... Type parameters can't be directly called on instances. Type members can be considered as named type parameters.

trait A[T]
val a: A[Int] = ???
type X = ?? // what is T of a?

trait A { type T }
val a: A { type T = Int } = ???
type X = a.T

trait A[_T] { type T = _T }
val a: A[Int] = ???
type X = a.T

• Type members variance can't be declared at the definition site, only at a call site (like for type parameters in Java)

trait A[+T] // definition

trait A[-T] // definition

trait A[T]
type X[+T] = A[_ <: T] // call
type Y[-T] = A[_ >: T] // call

trait A { type T }
type X[+_T] = A { type T <: _T } // call
type Y[-_T] = A { type T >: _T } // call

In Scala3, if generic type argument(s) is mapped to dependent type, how are covariant & contravariant modifiers mapped?

• The difference is in partial application. For trait MyTrait { type A; type B; type C } you can specify some of types and not specify others. But for trait MyTrait[A, B, C] you can only either specify all of them or not specify any of them. So type parameters are more like inputs (to be specified) and type members are more like outputs (to be inferred).

When are dependent types needed in Shapeless?

Why do we need to specify a refined type (or its equivalent Aux) for the output of certain type computations?

Why is the Aux technique required for type-level computations?

• There are differences in type inference for type parameters and type members. A type parameter should be inferred and if it can't be inferred it's minimized (for example Nothing). But a type member can remain abstract.

What's different between "def apply[T](c:T)" and "type T;def apply(c:T)"

Aux-pattern usage compiles without inferring an appropriate type

Why Scala Infer the Bottom Type when the type parameter is not specified? (answer)

• Also there can be differences in implicit resolution for type-parameter and type-member type classes (functional dependencies i.e. in trait A[T] { type S } type S can sometimes depend on T functionally while in trait A[T, S] the types T, S are arbitrary, class A t s | t -> s or class A t where type S t vs. class A t s in Haskell).

https://github.com/lampepfl/dotty/issues/17212

https://github.com/scala/bug/issues/12767

• Also type-parameter and type-member generalized algebraic types (GADT) are different

Scala 3. Implementing Dependent Function Type

https://github.com/lampepfl/dotty/issues/17235

• How in Scala 3 type parameters were going to be encoded as type members and why finally it was decided not to do so

https://dotty.epfl.ch/docs/internals/higher-kinded-v2.html

https://contributors.scala-lang.org/t/scala-3-type-parameters-and-type-members/3472

Bartram

Answer 5

I think that there's not much difference here. Type abstract members can be seen as just existential types which is similar to record types in some other functional languages.

For example, we have:

class ListT {
  type T
  ...
}

and

class List[T] {...}

Then ListT is just the same as List[_]. The convience of type members is that we can use class without explicit concrete type and avoid too many type parameters.

Gefen