Is F -bound polymorphism useful?

Language Design
#1

Is F - bound polymorphism actually useful, when you can refine return types in sub traits / classes without it? It certainly doesn’t seem to justify its weight in terms of complicating the source code. It seems the main purpose of F bound is to restrict the return types in sub classes.

Recently I’ve taken to using a type member if the return type is used in more than one method. So far this seems to work much better than F type.

In one place, where in the past I would have used F-Bound I’ve used the type member:

trait TGrid[TileT]
{ type GridT[A] <: TGrid[A]

This gives me a warning to enable the implicit value scala.language.higherKinds. What purpose does the warning serve? Will this code not work in Dotty? On the other hand an F-Bound type, which always seems to add significant complexity, and it would seem good, to discourage beginners from using, requires no special feature import.

2 Likes
#2

Java has F-bounded polymorphism. For that alone, Scala needs to have it for interoperability. Unfortunately, this trumps any consideration about whether they are too complex and/or otherwise replaceable. I believe that if Java was not in the picture, F-bounded polymorphism wouldn’t have survived this long in Scala.

1 Like
#3

It will work, the original idea of warning about things like higher kinds was to have clearly defined “language levels” to use for teaching Scala. Unfortunately the end result is that people consider all language warnings as noise and ignore them (-language:_), so I think we should just get rid of the higherKinds warning (and replace it with warnings for stuff that will in fact be deprecated/removed in Dotty, like wildcard applications of higher kinds).

7 Likes
#4

Isn’t that still f-bounded polymorphism*? It should be isomorphic to this f-bounded trait:

trait TGrid[TileT, GridT[A] <: TGrid[A, GridT]]

Most of the time the one with the type member should be a lot nicer at the use site. The unfortunate thing is that you can’t use a type member in the self-type.

* to really be the same thing I guess you’d need to have this:

trait TGrid[TileT] { 
  self => 

  type GridT[A] <: TGrid[A] { type GridT[A] = self.GridT[A] } 
}

So it’s basically a weaker version of f-bounded polymorphism.

1 Like
#5

The language.higherKinds import was introduced in 2.10 since at the time there was still some uncertainty about the stability of higher-kinded types in Scala. I could not explain it better than the doc-comment:

  /** Only where this flag is enabled, higher-kinded types can be written.
   *
   *  '''Why keep the feature?''' Higher-kinded types enable the definition of very general
   *  abstractions such as functor, monad, or arrow. A significant set of advanced
   *  libraries relies on them. Higher-kinded types are also at the core of the
   *  scala-virtualized effort to produce high-performance parallel DSLs through staging.
   *
   *  '''Why control it?''' Higher kinded types in Scala lead to a Turing-complete
   *  type system, where compiler termination is no longer guaranteed. They tend
   *  to be useful mostly for type-level computation and for highly generic design
   *  patterns. The level of abstraction implied by these design patterns is often
   *  a barrier to understanding for newcomers to a Scala codebase. Some syntactic
   *  aspects of higher-kinded types are hard to understand for the uninitiated and
   *  type inference is less effective for them than for normal types. Because we are
   *  not completely happy with them yet, it is possible that some aspects of
   *  higher-kinded types will change in future versions of Scala. So an explicit
   *  enabling also serves as a warning that code involving higher-kinded types
   *  might have to be slightly revised in the future.
   *
   *  @group production
   */
  implicit lazy val higherKinds: higherKinds = languageFeature.higherKinds

Things did change for higher klnds (e.g. SI-2712, new syntax for type lambdas) but much less than one
might have anticipated. Dotty and Scala-2 have by-and-large the same treatment of higher-kinded types. So I believe the language import should no longer be required (and in fact it isn’t required in Dotty).

F-bounds do indeed add significant complexity. I would love to be able to get rid of them, and replace them with higher-kinded subtyping in the way it is done in the TGrid example. But I don’t know how to handle the breakage of compatibility and Java interop. That looks like a daunting problem.

5 Likes
#6

So this would be an F -bounded type member as opposed to an F-bounded type member? Does this give practical extra type safety and power over my version, and would this avoid the pain-in the arseness of traditional F-bound type parametrisation?

I’m less concerned about removing F-bound type parameters, than teaching beginners alternatives. If I’d been told early in my OO learning that you can refine method return types in sub classes it would have been very helpful. I doubt many beginners are going to stumble on F-Bound type parameters through their own experimentation, if they use them it will almost certainly be because they’ve read the technique on a blog or in a tutorial. - or picked them up from Java.

1 Like
#7

I’m less concerned about removing F-bound type parameters, than teaching beginners alternatives.

F-bounded polymorphism parameterizes a type over its own subtypes, which is a weaker constraint than what the user usually wants, which is a way to say “my type”, which you can’t express precisely via subtyping. However typeclasses can express this idea directly, so that’s what I would teach beginners (even though there’s a bit of ceremony to deal with in Scala 2).

I wrote a tiresome blog post about this a long time ago. TL;DR is the paragraph above.

rob

8 Likes
#8

For some cases sub typing is best combined with a type class. For example:

trait Transer extends Any
{ def fTrans(f: Vec2 => Vec2): Transer
}

/** The typeclass trait for transforming an object in 2d geometry. */
trait Trans[T]
{ def trans(obj: T, f: Vec2 => Vec2):  T
}

/** The companion object for the Trans[T] typeclass, containing instances for common classes. */
object Trans {
  implicit def TransFromTranserImplicit[T <: Transer]: Trans[T] =
    (obj, f) => obj.fTrans(f).asInstanceOf[T]

  implicit def ArrTrans[A](implicit ct: ClassTag[A], ev: Trans[A]): Trans[Arr[A]] =
(obj, f) => obj.map(el => ev.trans(el, f))

etc etc
}

So just by subtyping the return type in the leaf classes:

/** Immutable Graphic element that defines, fills a Polygon. */ 
case class PolyFill(verts: Polygon, colour: Colour, zOrder: Int = 0) extends PolyElem
{ override def fTrans(f: Vec2 => Vec2): PolyFill = PolyFill(verts.fTrans(f), colour, zOrder) }

You get an automatic type class instance for every LUB, with no additional boilerplate. To do this without sub-typing would I believe require an explicit instance for every leaf class and every possible LUB.

#9

Your approach seems like an anti-pattern to me, because the unsafe cast may very well crash at runtime (if someone implements their fTrans by returning an instance of a different class).
You just need to parameterize Transer with a self-type using an F-bound to make it work, though:

trait Transer[Self <: Transer] extends Any {
  def fTrans(f: Vec2 => Vec2): Self
}
case class PolyFill(verts: Polygon, colour: Colour, zOrder: Int = 0)
  extends Transer[PolyFill] { ... }
1 Like
#10

It doesn’t seem to, to me. So frequently I’ve copied pasted a Transer class modified but forgot to change the return type on fTrans. In practice it never compiles because the constructor signatures don’t match. But even with this contrived example:

case class BadTranser(i: Int = 0) extends Transer
{ def fTrans(f: Vec2 => Vec2): GoodTranser = GoodTranser(i)
}

case class GoodTranser(i: Int = 0) extends Transer
{ def fTrans(f: Vec2 => Vec2): GoodTranser = GoodTranser(i)
}

val b1 = BadTranser(1)
val b2 = BadTranser(2)
val l = List(b1, b2).scale(5)
val ls = l.scale(3)
debvar(ls)
//NewGrid.scala.25.9. ls = List(GoodTranser(1), GoodTranser(2))

It doesn’t crash. So my contention is that F-bound type parametrisation is a massivley pain in the neck solution for a vanishingly rare problem.

#11

Try:

val b3 = implicitly[Trans[BadTranser]].trans(b2, identity)
1 Like
#12

I know it’s a necro, but I have fought with this problem extensively some time ago.

F-bounded polymorphysm is different from ‘self’ member type in the returned type.
If you have a type hierarchy and invoke a method returning ‘the same type’ for some abstract class a :A, in F-bounded polymorphysm the result is A. In bound type member approach, the result is a.Self. This matters in type inference, especially for implicits.

Compare:

   trait Base1[+Self <: FBound[Self]] {
      def copy :Self
   }
   trait Sub1 extends Base1[Sub1]
   class Impl1 extends Sub1 with Base1[Impl1] {
      def copy = this
   }

   trait Base2 {
      type Self <: Base
      copy :Self 
   }
   trait Sub2 extends Base2 { type Self <: Sub2 }
   class Impl2 extends Sub2 {
      type Self = Impl2
      def copy = this
   }

   def copy1[T <: Base1[T]](x :T) = x.self
   def copy2(x :Base2) = x.self
   
   val proto1 = new Impl1 :Sub1
   val proto2 = new Impl2 :Sub2
   val a = copy1(proto1)
   val b = copy2(proto2)

The type of a is Sub1, but the type of b is proto2.Self <: Sub2.
This can be an advantage of member types: method copy2 is simpler, and no matter
how specific an object you pass in, you’ll get a value of the exact same type.

It is however a huge pain when applied recursively:

   class Ev1[T <: Base1[T]] 
   implicit val sub1Ev = new Ev1

   class Ev2[T <: Base2] 
   val sub2Ev = new Ev2

   class Foo
   implicit def foo1[T <: Base1[T]](x :T)(implicit ev :Ev1[T]) = new Foo
   implicit def foo2[T <: Base2](x :T)(implicit ev :Ev2[T]) = new Foo
   def foo[T](x :T)(implicit ev:T => Foo) = ev(x)
  
   foo1(proto1.self) //compiles
   foo2(proto2.self) //does not compile

   foo(proto1.self) //ok
   foo(proto2.self)  //implicit not found

The implicit case is a pain, because now always possibility to specify the type arguments manually. Depending on complexity of the actual case, it is often possible to do some tricks in order to guide the compiler, but it takes quite a bit of experience, time, and method signatures are much more complicated.