logji

noodling towards a functional brain

Thursday, November 29, 2012

F-Bounded Type Polymorphism Considered Tricky

This post is intended to address a question that I seem to see come up every few months on the Scala mailing
list or the #scala IRC channel on freenode. The question is often posed in terms of the phrase
"recursive type" and usually involves someone having some difficulty or other (and many arise) with
a construction like this:

```trait Account[T <: Account[T]] {
def addFunds(amount: BigDecimal): T
}

class BrokerageAccount(total: BigDecimal) extends Account[BrokerageAccount] {
def addFunds(amount: BigDecimal) = new BrokerageAccount(total + amount)
}

class SavingsAccount(total: BigDecimal) extends Account[SavingsAccount] {
def addFunds(amount: BigDecimal) = new SavingsAccount(total + amount)
}
```

This sort of self-referential type constraint is known formally as F-bounded type polymorphism and is usually attempted when someone is
trying to solve a common problem of abstraction in object-oriented languages; how to define a polymorphic
function that, though defined in terms of a supertype, will when passed a value of some subtype will always
return a value of the same subtype as its argument.

It's an interesting construct, but there are some subtleties that can trip up the unwary user, and which make
naive or incautious use of the pattern problematic. The first issue that must be dealt with is how to
properly refer to the abstract supertype, rather than some specific subtype. Let's begin with a simple
example; let's say that we need a function that, given an account, will apply a transaction fee for adding
funds below a certain threshold.

```object Account {
val feePercentage = BigDecimal("0.02")
val feeThreshold = BigDecimal("10000.00")

def deposit[T <: Account[T]](amount: BigDecimal, account: T): T = {
if (amount < feeThreshold) account.addFunds(amount - (amount * feePercentage))
}
}
```

This is straightforward; the type bound is enforced via polymorphism at the call site. You'll notice that the
type ascribed to the "account" argument is T, and not Account[T] - the bound on T gives us all the constraints
that we want. This does what we want it to do when we're talking about working with one account at a time.
But, what if we want instead to perform some action with a collection of accounts of varying types; suppose
we need a method to debit all of a customer's accounts for a maintenance fee? We can expect our type bounds
to hold, but things begin to get a little complicated; we're forced to use bounded existential types.
Here is the correct way to do so:

```object Account {
def debitAll(amount: BigDecimal, accounts: List[T forSome { type T <: Account[T] }]): List[T forSome { type T <: Account[T] }] = {
accounts map { _.addFunds(-amount) }
}
}
```

The important thing to notice here is that the type of individual members of the list are existentially
bounded, rather than the list being existentially bounded as a whole. This is important, because it means
that the type of elements may vary, rather than something like "List[T] forSome { type T <: Account[T] }"
which states that the values of the list are of some consistent subtype of T.

So, this is a bit of an issue, but not a terrible one. The existential types clutter up our codebase and
sometimes give the type inferencer headaches, but it's not intractable. The ability to state these existential
type bounds does, however, showcase one advantage that Scala's existentials have over Java's wildcard types,
which cannot express this same construct accurately.

The most subtle point about F-bounded types that is important to grasp is that the type bound is *not*
as tight as one would ideally want it to be; instead of stating that a subtype must be eventually
parameterized by itself, it simply states that a subtype must be parameterized by some (potentially
other) subtype
. Here's an example.

```class MalignantAccount extends Account[SavingsAccount] {
def addFunds(amount: BigDecimal) = new SavingsAccount(-amount)
}
```

This will compile without error, and presents a bit of a pitfall. Fortunately, the type bounds that we
were required to declare at the use sites will prevent many of the failure scenarios that we might be

```object Test {
def main(argv: Array[String]): Unit = {
Account.deposit(BigDecimal("10.00"), new MalignantAccount)
}
}

nuttycom@crash: ~/tmp/scala/f-bounds \$ scalac Test.scala
Test.scala:27: error: inferred type arguments [MalignantAccount] do not conform to method deposit's type parameter bounds [T <: Account[T]]
deposit(BigDecimal("10.00"), new MalignantAccount)
^
one error found
```

but it's a little disconcerting to realize that this level of strictness is *only* available at the use site,
and cannot be readily enforced (except perhaps by implicit type witness trickery, which I've not yet tried)
in the declaration of the supertype, which is what we were really trying to do in the
first place.

Finally, it's important to note that F-bounded type polymorphism in Scala falls on its face when you start
talking about higher-kinded types. Suppose that one desired to state a supertype for Scala's structurally
monadic types (those which can be used in for-comprehensions):

```trait Monadic[M[+_] <: ({ type λ[+α] = Monadic[M, α] })#λ, +A] {
def map[B](f: A => B): M[B]
def flatMap[B](f: A => M[B]): M[B]
}
```

This fails to compile outright, complaining about cyclic references in the type constructor M.

In conclusion, my experience has been that F-bounded type polymorphism is tricky to get right and causes typing clutter in the codebase. That isn't to say that it's without value, but I think it's best to consider very carefully whether it is actually necessary to your particular application before you step into the rabbit hole. Most of the time, there's no wonderland at the bottom.

EDIT:

Heiko asks below why not use the following definition of debitAll:

```object Account {
def debitAll2[T <: Account[T]](amount: BigDecimal, accounts: List[T]): List[T] = {
accounts map { _.addFunds(-amount) }
}
}
```

The problem here is that this has a subtly different meaning; this says that for debitAll2, all the members
of the list must be of the *same* subtype of Account. This becomes apparent when we actually try to use the
method with a list where the subtype varies. In both constructions, actually, you end up having to explicitly
ascribe the type of the list, but I've not been able to find a variant for the debitAll2 where the use site
will actually compile with such a variant-membered list.

```object Test {
def main(argv: Array[String]): Unit = {
// compiles, though requires type ascription of the list; this is where the inferencer breaks down.
Account.debitAll(BigDecimal("10.00"), List[T forSome { type T <: Account[T] }](new SavingsAccount(BigDecimal("0")), new BrokerageAccount(BigDecimal("0"))))

// doesn't compile
// Account.debitAll2(BigDecimal("10.00"), new SavingsAccount(BigDecimal("0")) :: new BrokerageAccount(BigDecimal("0")) :: Nil)

// doesn't compile
// Account.debitAll2(BigDecimal("10.00"), List[T forSome { type T <: Account[T] }](new SavingsAccount(BigDecimal("0")), new BrokerageAccount(BigDecimal("0"))))
}
}
```

1. Hey Kris,

Excellent writeup.

One question: Why didn't you define debitAll polymorphic?
def debitAll[T <: Account[T]](... accounts: List[T]...

Cheers
Heiko

1. Hi, Heiko, I've added a bit to clarify this point. Thanks for asking!

2. I wonder why you wouldn't just use Account[_] in these cases?

That said, I agree that F-bounded polymorphism can easily have a lot of pitfalls (although I must confess to having a soft spot for it, myself).

1. Scala interprets that as really being Account[T] forSome { type T } - that is, if you use the addFunds function on such a beast, you don't get back what you expect you would get back. Try it! defining debitAll in terms of List[Account[_]] means that you get a compile error from the line "accounts map { _.addFunds(-amount) }" - what you get back is a List[Any], because the compiler literally infers just Any (with no bounds) for that parameter. That's where the trickiness comes in - the forSome syntactic sugar doesn't respect bounds on the declaration site of that type!

3. Kris,

One can avoid the ugliness and limitations of the type inferencer by using type members instead of type parameters:

trait Foo {
type SpecialFoo <: Foo
def foo: SpecialFoo
}

class Bar extends Foo {
type SpecialFoo = Bar
def foo = this
}

class Baz extends Foo {
type SpecialFoo = Baz
def foo = this
}

object Test extends App {
def withFoos(foos: List[Foo]) = foos
val foos = List(new Bar, new Baz)
println(withFoos(foos).last.foo)
}

1. Yup, absolutely. This is, in fact, the essence of the Cake pattern. One thing to note though is that this still doesn't avoid the MalignantAccount case; the bound isn't sufficiently restrictive for the declaration site to be able to enforce anything meaningful about the relationship. The way forward here is actually via the Cake pattern; I'll probably do a follow-up post on its application to this problem here in a few days.

4. Very interesting read, thanks a bunch!

5. Couldn't you self type your Account to T in order to avoid the MalignantAccount case?

trait Account[T <: Account[T]] {
self: T =>

def addFunds(amount: BigDecimal): T

}

6. Very good article!

More pitfalls:
1. Compiler stack overflow when using Manifest with f-bounded and existential types : https://issues.scala-lang.org/browse/SI-6255

2. As you said, you cannot use Account[_] because it translates into `Account[T] forSome { type T } ]`, which gives you an un-bounded T. There's basically no easy way to define "Any Account". You can alias your existential into the companion object, but then...

3. Defining the "Account.Any" type is forcing you into covariance.
If you don't want to carry around declarations such as `T forSome { type T <: Account[T] }` you end up writing something like :

object Account {
type Any = Account[T] forSome { type T <: Account[T] }
}

Then if you want to return any account:

trait Account[T <: Account[T]] {
def x() : Account.Any
}

class SomeAccount extends Account[SomeAccount] {
def x() = if( true ) new SavingsAccount(...) else new SomeAccount
}

This will break unless you define Account as covariant: `trait Account[+T <: Account[T]]`

7. As you wrote in your response to Heiko, using abstract type member is not a viable solution.

As we concluded that neither f-bounded type nor abstract type member work well, I believe the workaround would be overriding methods in subclasses to return proper types. This of course only works to some extent and requires boilerplate code but I find it quite relevant with sealed data structures. At least this won't pollute your client code.

Here is a simple example:

sealed abstract class Account {
def aGenericOperationThatShouldReturnTheOriginalAccount : Account = { /* generic implementation */ }
}

class MyAccount extends Account {
override def aGenericOperationThatShouldReturnTheOriginalAccount = super.aGenericOperationThatShouldReturnTheOriginalAccount.asInstanceOf[MyAccount] // bouuuh an ugly cast! but my client code look nice :)
}

8. Good article - it highlights the problem very well. If I may, I would like to add a generic solution to the problem:

"How to avoid f-bounded polymorphism"

F-bounded polymorphism occurs when a type expects *important interface changes* to be introduced in derived types.

This can be avoided by *composing* the unknown interface changes instead of attempting to support them as a derivative of the current type.

For example:

trait Aggregate[A <: Aggregate[A, E], E] {
def apply(event: E): A
}

becomes:

trait Aggregate[A, E] {
// Here, the derived type information is expected to be the aggregate root's properties.
// The previous example assumed this would be added through inheritance.
val root: A

def apply(event: E): Aggregate[A, E]
}

9. I have blogged about this issue (with workaround) here:
https://github.com/ljwagerfield/scala-type-inference

10. You could use type aliases to make the client code more succinct:

type BaseAccount = T forSome { type T <: Account[T] }

Then, your functions become:

def debitAll(amount: BigDecimal, accounts: List[BaseAccount]):List[BaseAccount] = {
accounts map { _.addFunds(-amount) }
}

Note: Only a member of this blog may post a comment.