Should variance annotations be used?

[Tony Morris]

I have this ongoing fence jumping issue with regard to variance annotations.

To start, at least, it seems that "use variance annotations" is an
all-in or nothing proposition. You either do or you do not -- there is
no in-between, since you otherwise run into disaster. I have accepted
this to be true and I shall assume that others have too.

Next, there are claims that type-inference is improved by accepting the
use of variance annotations. I have yet to see these claims come true in
a convincing way. Specifically, I do acknowledge that for some
use-cases, there is an improvement, however, often there is also an
associated cost on exactly the same goal -- type-inference.

I have had functors that are both covariant and contravariant, depending
on certain constraints; what now? Indeed, I have so many different
use-cases to cover with regard to this question that I am not even
confident that I could list them all in one go -- I won't even try. I
will just pose an initial question.

Too often, I think I have it figured out, then bammo, a new use-case
pops up that causes me to question the position and jump back on the fence.

I know there are some out there with stronger opinions on this matter
than myself and I truly wish I could do same. Some argue that some
amount of safety is lost. Some argue that certain useful libraries
cannot exist when you adopt a specific position. I just don't know.

I am seeking those opinions, then I hope to rebut them successfully or
not in an effort to resolve my ongoing conflict.

--
Tony Morris
http://tmorris.net/

[Stefan Hoeck]

I find variance annotations to be quite useful especially when working with libraries (such as the scala standard library) that use them. Since algebraic data types in Scala are typically modeled via inheritance (sealed trait or abstract class and then case objects and case classes extending this trait) they can be used more naturally with data structures that use variance annotations.
Variance can also have an effect on the number of objects being created. For instance: Since Option is covariant in its type parameter, None can be described as a singleton object extending Option[Nothing]. This would not work out if Option were invariant and therefore we'd either have to manually cast a hidden singleton object to the desired Option type or create a new None for every type parameter. The latter is not what I call memory efficient, the first is just plain ugly (which is a somewhat weak argument I know). So I stick to variance annotations - they feel more natural for me when working with Scala - and except the libraries I use to do the same.

I found it for instance to be quite cumbersome that IO in scalaz 6 was invariant instead of covariant. I'm quite happy that this was changed for scalaz 7.

So, from my point of view, pro or contra variance annotations is more a matter of taste than of hard facts. As far as I have experienced it, typically problems can be solved both ways where one way usually feels more natural and needs less additional type-parameter boilerplate. In the code I write, variance annotations typically mean less boilerplate.

Stefan

[Tony Morris]

Covariance can be eschewed with map: (A => B) => F[A] => F[B]
Contravariance can be eschewed with contramap: (A => B) => F[B] => F[A]

Sure, there might be allocation costs, but leaving this aside, I am most
interested in the implications for the type system and how it plays out
in practice. It seems I can appeal to existing literature on type
theory, but it falls far short of answering the question, "how to best
use Scala with regard to variance?" It is this huge gap that I would
love to fill in. Should we say that Scala has two type systems (variance
annotation/inheritance vs map/contramap) that do not unify? Let's not
even get started on the evaluation models (call-by-name, etc) here with
regard to unification.

Some say, yes definitely, use it. Others say no, definitely do not use
it. In both cases, I can construct a rebuttal that I do not know the
answer for.

IO is declared invariant. You have IO[A] and "A inherits from B" and you
want IO[B]. If we get rid of inheritance and where it is instead
modelled as =>, then you'd have IO[A] and "A => B" and you want IO[B].
Easy peasey: map. Yeah it's three letters for what would otherwise be
implicit (shame the . keyword is taken eh?), but why should map get
special treatment with regard to even having language keywords
(extends/with) anyway?

Existing Scala libraries have both variance/inheritance annotation and
map. But even ignoring the built-in libraries (which I find almost
always need rewriting when it comes to practical application for other
reasons anyway), what would be the approach if you were to start from
scratch? Would you use variance annotations, map/contramap, both,
something else?

It boggles my mind. So many questions. Comments most appreciated.

[Matthew Pocock]

On 5 October 2012 10:42, Tony Morris <tonym...@gmail.com> wrote:

IO is declared invariant. You have IO[A] and "A inherits from B" and you
want IO[B]. If we get rid of inheritance and where it is instead
modelled as =>, then you'd have IO[A] and "A => B" and you want IO[B].
Easy peasey: map. 

Sure, and we could use an implicit conversion that delegates to an implicit <:< instance to drop 'widening' in to simulate co-/contra-variance. There will be significant run-time overheads to this, in terms of objects allocated and chaining functions together (that a good optimizing compiler should be able to ameliorate), and I generally find it much easier to debug issues in types than issues with implicits - there is no 'debug implicits' mode available in any of the IDEs - coding is about maintainability, not just expressivity.

Matthew

--

Dr Matthew Pocock

Integrative Bioinformatics Group, School of Computing Science, Newcastle University

mailto: turingate...@gmail.com

mailto: matthew...@ncl.ac.uk

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

skype: matthew.pocock

tel: (0191) 2566550

mob: +447535664143

[Stefan Hoeck]

I think the root of the problem is the two ways to model an 'is a' relationship in scala: Functional via A => B or 'object-oriented' via inheritance. Since at least some things in Scala are typically modeled using inheritance (ADTs), we need variance annotations.

Now, if we could start from scratch and if there were no allocation costs and if we wouldn't mind the additional three and nine letter words map and contramap, then yes, describing co- and contravariance solely via functors would be an option. But these are three big 'ifs'. Personally, I wish Scala were purely functional, some sort of improved Haskell with some of Haskell's inconsistencies removed (like monads being automatically applicatives). But alas! Scala is what it is, so at least two of the three ifs above are a given as far as I see it (we probably could start from scratch library-wise though).

So, as I see it what we'd need is some kind of mechanism - both elegant and efficient - to describe ADTs without using inheritance. Then there would be no such thing as type None or type Some[A] but only Option[A] and therefore no need for variance annotations in purely functional code.

Stefan

2012/10/5 Tony Morris <tonym...@gmail.com>

--
You received this message because you are subscribed to the Google Groups "scala-functional" group.
To unsubscribe from this group, send email to scala-function...@googlegroups.com.

[Sébastien Bocq]

2012/10/5 Tony Morris <tonym...@gmail.com>

I'm not comfortable with these annotations either. For example, the extra complexity variance annotations place on common method signatures like List[+A]#append[B >: A](l:List[B]):List[B] keeps on bothering me and I always feel a bit embarrassed when I have to explain this part to newcomers...

If I had the time, I'd experiment with type safe implicit coercions. It is just an idea. I don't know how well it would work on more complex examples but here is the gist of it:

trait Covariant[M[A], A] {
  def coerce[B >: A]:M[B] = this.asInstanceOf[M[B]]
}

trait CovariantImplicits[M[A] <: Covariant[M, A]] {
  implicit def coerce[A, B >: A](m:M[A]):M[B] = m.coerce
}

abstract class Maybe[A] extends Covariant[Maybe, A]
case class Just[A](a:A) extends Maybe[A]
case object Empty extends Maybe[Nothing]

object Maybe extends CovariantImplicits[Maybe]

scala> class B
defined class B

scala> class A extends B
defined class A

scala> val ma:Maybe[A] = Empty
ma: Maybe[A] = Empty

scala> val mb:Maybe[B] = ma
mb: Maybe[B] = Empty


Then I'd go on defining other traits like:

trait Contravariant[M[A], A] {
  def coerce[B <: A]:M[B] = this.asInstanceOf[M[B]]
}

trait Covariant2[M[A, B], A, B] {
  def coerce[C >: A, D >: B]:M[C, D] = this.asInstanceOf[M[C, D]]
}

trait ArrowVariant[M[_, _], A, B] {
  def coerce[C <: A, D >: B]:M[C, D] = this.asInstanceOf[M[C, D]]
}

There are some drawbacks but I think they are minor:

- You can get the variance wrong. For example, this will compile:

class O[A] extends Covariant[O, A] {
  def foo(a:A):Unit = sys.error("")
}
// covariant type A occurs in contravariant position

- Some error messages won't be accurate anymore e.g.:

scala> val ma:Maybe[A] = mb
<console>:14: error: type mismatch;
 found   : Maybe[B]
 required: Maybe[A]
Note: B >: A, but class Maybe is invariant in type A.
You may wish to define A as -A instead. (SLS 4.5)

Now, as I said earlier, I never carried out this experiment much further than that. This approach may not work in some cases or it may have severe limitations I haven't foreseen. If this is the case, I'm always interested to hear about them.

Cheers,
Sébastien

[Ben Hutchison]

On Fri, Oct 5, 2012 at 8:14 PM, Stefan Hoeck <efasc...@gmail.com> wrote:
> I think the root of the problem is the two ways to model an 'is a'
> relationship in scala: Functional via A => B or 'object-oriented' via
> inheritance. Since at least some things in Scala are typically modeled using
> inheritance (ADTs), we need variance annotations.

Strictly, variance doesn't have anything to do with inheritance.
Variance arises whenever you combine Subtyping + Parametrized Types.

Subtyping can arise without inheritance in structural typing. In
nominal typing (which is somewhat an artificial construction),
inheriting from a superclass introduces a subtype relationship, so
inheritance tends to get wrongly conflated with subtyping. But in
essence, subtyping is just about Set relations on the features defined
by a type: a subtype must posses at least the set of the features
exposed by it's supertype.

I think if you embrace subtyping, you must embrace variance. To
attempt otherwise would be futile - it will simply manifest under a
different guise. As to whether subtyping is useful - it's a much
debated topic, but I'm personally in the embrace-subtyping camp.

My belief is based on an personal intuition that subtype relations in
pure form, as relations between sets of features, are an innate,
undeniable mathematical truth, and not some artificial model imposed
by human fancy and values (as object-orientation is). I realize that's
not a logical argument; I offer it only as an explanation of my own
beliefs.

-Ben

[eugene yokota]

Variance annotations combined with Scala typeclasses adds different semantics. If subtyping can be described as "is-a" relationship, I like to think of typeclasses to be "can" relationship.

For example, CanShow[A] means type A can show itself as a String. Defining CanShow[+A] expands "can" relationship to "can for all of its supertypes" and defining CanShow[-A] expands to "can for all its subtypes." 

For describing the capabilities of algebraic data types (ADT), I figured contravariance would be the one that could be useful, so I implemented CanEqual[-A] and CanShow[-A]: https://gist.github.com/3850520

To try it, go into the REPL's paste mode, and paste the contents:

    scala> :paste

    // Entering paste mode (ctrl-D to finish)

    trait CanEqual[-A]  {

      def equals(a1: A, a2: A): Boolean

    }

    ....

Show typeclass works out well:

    scala> Red.show

    res0: String = Red

Red is a case object that extends TrafficLight, and it's able to use TrafficLightShow. The problem is the Equal.

    scala> Red === Green

    <console>:30: error: inferred type arguments [Green.type] do not conform to method ==='s type parameter bounds [B <: Red.type]

                  Red === Green

                      ^

    <console>:30: error: type mismatch;

     found   : Green.type

     required: B

                  Red === Green

                          ^

CanEqual[TrafficLight] is availble for both Red and Green, but I couldn't figure out how to define ===. Due to contravariance Red.type quialifies itself to become CanEqualOps[Red.type]. What it allows us to do is to drop the type annotation for right hand side that's normally needed:

    scala> (Red: TrafficLight) === Green

    res2: Boolean = false 

This asymmetry stands out for List:

    scala> List(1) === Nil

    res3: Boolean = false

    scala> Nil === List(1)

    <console>:30: error: inferred type arguments [List[Int]] do not conform to method ==='s type parameter bounds [B <: scala.collection.immutable.Nil.type]

                  Nil === List(1)

                      ^

    <console>:30: error: type mismatch;

     found   : List[Int]

     required: B

                  Nil === List(1)

                              ^

    scala> (Nil: List[Int]) === List(1)

    res5: Boolean = false

Unless such asymmetry can be resolved, variance could actually be more confusing, or plain wrong.

-eugene

[Ben Hutchison]

Hi Eugene,

Thanks for an informative and thought-provoking example. 

After looking at your example, I believe the cause lies not with variance, but with the implicit-wrappers that allow functions to be used in infix position by "dressing up" the call in Scala's object-oriented style.

Your === is (in intent) a symmetric binary function of two values. But when you invoke via wrapper 

trait CanEqualOps[A] 

...you are saying "solve for A" based /only on type of the first parameter/. That's where the asymmetry comes in that makes === go wrong.

Contrast this with a scenario where we solve for a type A based on both parameters, eg extending your gist:

scala> object Equalifier { def eq[A](a: A, b: A)(implicit ev: CanEqual[A]) = ev.equals(a, b)}

defined module Equalifier

scala> Equalifier.eq(Red, Green)

res0: Boolean = false

So I reckon this problem is a consequence of the asymmetry of object-oriented dispatch, rather than variance itself.

-Ben

--

[Tony Morris]

There are some strong opinions that are missing from this discussion.

[Ben Hutchison]

This problem - making a contravariant Equals[A] typeclass that "just works" - has been troubling me since our discussion. 

Im troubled because there are lots of real-life binary functions that operate on 2 arguments and should be symmetric, equals being an example. The "scala way" to represent such binary functions seems to be via implicit wrappers to dress up the call as (asymmetric) OO dispatch on the first argument, rather than by allowing functions to be used in infix position (ie written between their 2 arguments). But if implicit wrappers cannot, reliably and fuss-free, emulate the behaviour we would achieve by invoking the function directly, Scala's support for typeclass-based programming is quite compromised.

Hence, I'm quite relieved to have found an apparent resolution of the difficulties Eugene raised: [https://gist.github.com/3984314] A restructuring of the implicit wrapper, that does allow "Red == Green" to typecheck, and use an CanEqual[TrafficLight] to compute equality. 

The essence of it lies in resolving the typeclass instance only once we have the second argument available, and can thus compute a common (contravariant) supertype C:

trait CanEqualOps[A] {
  final def ===[B <: C, C >: A](other: B)(implicit ev: CanEqual[C]): Boolean = ev.equals(self, other)
}

Now, I note that Scalaz 7 doesn't use this pattern, eg [https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/syntax/EqualSyntax.scala]. In fact, Scalaz 6.x was closer to this [http://scalaz.github.com/scalaz/scalaz-2.9.1-6.0.4/doc.sxr/scalaz/Identity.scala.html]. 

Are there other design forces that drive the decision to resolve the typeclass earlier (ie when the first argument is wrapped) in Scalaz?

-Ben

[Miles Sabin]

On Wed, Oct 31, 2012 at 3:44 AM, Ben Hutchison <brhut...@gmail.com> wrote:
> The essence of it lies in resolving the typeclass instance only once we have
> the second argument available, and can thus compute a common (contravariant)
> supertype C:
>
> trait CanEqualOps[A] {
> final def ===[B <: C, C >: A](other: B)(implicit ev: CanEqual[C]): Boolean
> = ev.equals(self, other)
> }

Why the fiddly bounds here? Why not something like,

trait CanEqualOps[A] {
final def ===[B](other: B)(implicit ev: CanEqual[A, B]): Boolean = ...
}

and then let the CanEqual instances determine the relation at both
type and value levels?

Cheers,


Miles

--
Miles Sabin
tel: +44 7813 944 528
skype: milessabin
gtalk: mi...@milessabin.com
g+: http://www.milessabin.com
http://twitter.com/milessabin