Pull request review

[Lars Hupel]

Dear list,

I filed pull request #383 because there's a broad consensus that type
constructor variance annotations (e.g. in transformers) cost more than
they benefit us.

However, those changes necessitated further, partially unexpected
changes in some of our data types. For example, `IO` is now invariant.
Some of these data types can be made covariant again, if desired.

Assume this simple data type:

trait Foo[+A] {
// ...

def frobnicate: OptionT[List, A] = ...
}

This won't compile anymore, because `A` appears in invariant position
now. Generally, there are two ways how to tackle these issues:

1) make `Foo` invariant
2) give `frobnicate` a new type parameter `AA >: A`, and change the
return type `OptionT[List, AA]`

In the scalaz codebase, I chose 2) wherever feasible (i.e. where it only
involved changing a couple of methods), otherwise 1).

Both alternatives are source-incompatible. 2) breaks when you specify
explicit type parameters, so in that case, you have to add another one
at call sites. In some cases, you have to add type parameters to aid
type inference. For 1), the fix is "viral": usually, making things
invariant involves making more things invariant.

I'm open to suggestions, so please review the changes and discuss the
code at: <https://github.com/scalaz/scalaz/pull/383>.

I intend to merge this prior to the release of the first milestone of
7.1.0 (expect a release candidate for 7.0.1 soon, too, but that won't
incorporate variance changes).

Regards
Lars

[Miles Sabin]

On Sun, Jun 2, 2013 at 6:14 PM, Lars Hupel <hu...@in.tum.de> wrote:
> Assume this simple data type:
>
> trait Foo[+A] {
> // ...
>
> def frobnicate: OptionT[List, A] = ...
> }
>
> This won't compile anymore, because `A` appears in invariant position
> now. Generally, there are two ways how to tackle these issues:
>
> 1) make `Foo` invariant
> 2) give `frobnicate` a new type parameter `AA >: A`, and change the
> return type `OptionT[List, AA]`

You missed,

3) Move the problematic methods to an invariant FooOps trait and
enrich them back on to Foo,

trait Foo[+A] {
// ...
}

object Foo {
implicit def fooOps[A](foo: Foo[A]) = new FooOps(foo)

class FooOps[A](foo: Foo[A]) {

def frobnicate: OptionT[List, A] = ...
}
}

This is a very generally applicable technique which for some reason
doesn't seem to be all that widely known. It's used heavily in
shapeless: for instance, it's what enables the covariance of shapeless
HLists despite their type arguments being used in both co- and
contravariant positions in the various HList operations.

Cheers,


Miles

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

[Paul Chiusano]

I am not in favor of merging this change, or really any major change involving how we handle variance in scalaz, until we have a totally methodical writeup of exactly what the problems are with using variance annotations, along with a writeup of what has been tried and been shown not to work, and why. I feel like we are just acting on hearsay and a vague impression that "variance is hard, let's go shopping". 

Here is a proposal that I don't think has been fully explored:

Change Functor, Applicative, etc, to take a covariant type constructor - trait Functor[F[+_]] { ... }. Any type that is a functor is obviously covariant - to go from F[Dog] to F[Animal], just map the identity function over it! And likewise for types with a contramap - these type constructors can be made contravariant. Then make related changes to the monad transformers and elsewhere. I just think something is really wrong if we end up having to make an obviously covariant type like IO invariant. 

I think most of the problem is that OO encourages dumping a bunch of functions inside the body of the class for syntactic convenience, but which conflict with the correct variance annotation. The way to solve that is not to make things invariant, but to just give things the correct types, with LUBs and/or moving things to a FooOps class in the companion object, like Miles suggests. That approach works out great and I've used it plenty. If you put the implicit in the companion object, you don't even need an explicit import and users of the class can't even 'tell' what's a native function and what's a pimped function. 

I'd like to see this worked through in detail, for all of scalaz. It's obviously a breaking change, but it seems like The Right Thing. And if this doesn't work out for some reason, I want to understand why.

Paul

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scalaz+un...@googlegroups.com.
To post to this group, send email to sca...@googlegroups.com.
Visit this group at http://groups.google.com/group/scalaz?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

[Stephen Compall]

Sorry for prior empty message, dupes, anything else that happens (thanks
google).

Paul Chiusano <paul.c...@gmail.com> wrote:

>I am not in favor of merging this change, or really any major change
>involving how we handle variance in scalaz, until we have a totally
>methodical writeup of exactly what the problems are with using variance
>annotations, along with a writeup of what has been tried and been shown
>not
>to work, and why. I feel like we are just acting on hearsay and a vague
>impression that "variance is hard, let's go shopping".

I don't think so; https://issues.scala-lang.org/browse/SI-2066 is real,
kind variance is backwards approximately half of the time (it doesn't
flip in contra-kind-variant positions), Scala 2.11 is if anything *more*
schizophrenic about kind variance (wrt bounds see
https://issues.scala-lang.org/browse/SI-6169 for lots of fun), and your
only hope is bending your mind around polykinds (Pythonically, because
scalac won't help you), hoping you got it right, and that you won't run
into scalac thinking *only* inconsistent things are consistent & vice
versa at the same time.

I'd prefer to think in the more consistent subset of Scala that doesn't
have polykinds, until we have a substrate that's worked those issues
out.

>trait Functor[F[+_]] { ... }. Any type that is a functor is obviously
>covariant - to go from F[Dog] to F[Animal], just map the identity
>function
>over it! And likewise for types with a contramap - these type
>constructors
>can be made contravariant. Then make related changes to the monad
>transformers and elsewhere. I just think something is really wrong if
>we
>end up having to make an obviously covariant type like IO invariant.

Yes, but I propose that Scala's implementation of variance is the thing
that is really wrong, and it must be fixed there before we can safely
use it here.

>not
>to make things invariant, but to just give things the correct types,
>with
>LUBs and/or moving things to a FooOps class in the companion object,
>like
>Miles suggests. That approach works out great and I've used it plenty.

I'm in favor of Miles's suggestion, if only because I really dislike
Scala 2.10 Option#fold.

>If
>you put the implicit in the companion object, you don't even need an
>explicit import and users of the class can't even 'tell' what's a
>native
>function and what's a pimped function.
>
>I'd like to see this worked through in detail, for all of scalaz. It's
>obviously a breaking change, but it seems like The Right Thing. And if
>this
>doesn't work out for some reason, I want to understand why.

Obviously, I'm loath to sit around the bug tracker, if only because I've
experienced things like https://issues.scala-lang.org/browse/SI-6260 too
often. I'm happy to talk about cataloguing and formalizing more of these
issues. Much of it's a tarpit, though, considering e.g.
https://issues.scala-lang.org/browse/SI-7318 is not a bug (there seems
to be a dichotomy here regarding variance Dan Doel understands better
than I).

Anyway, I'd rather see work towards values over universally quantified
type, Haskell-style, than further efforts towards fixing kind variance
in scalac.

--
Stephen Compall
"^aCollection allSatisfy: [:each | aCondition]": less is better than

[Chris Marshall]

Can you elaborate a bit on the sort of code which used to compile but which now will not do so? 

I really don't think that scalaz should be making other major changes so soon after the v7 upgrade pain. If it's source-compatible (or trivial to modify), fine, otherwise, please no.

Most of the "scala is so much more productive" argument disappears down the toilet if you spend a lot of time on upgrade cycles

Chris

On Sun, Jun 2, 2013 at 6:14 PM, Lars Hupel <hu...@in.tum.de> wrote:

Lars

[Tony Morris]

There are three situations:

1) Use variance annotations
2) Do not use variance annotations
3) Use woteva

We are currently in situation 3). This is the worst of situation of the three.

As for deciding between 1) and 2) I have never had a strong position. This is because every time I would try to come up with an argument in either direction, I could also counter-argue it. However, I admit to my position growing recently toward 2). This is because the counter-arguments are relatively weak as piss. I will hold off on this point for now -- maybe there is something I am missing (it is discussed a lot).

However, this pull request gets us out of position 3), which is worst of all -- I am strongly in favour of it for this reason. Not necessarily because it gets us to position 2), although that might be where we end anyway.

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

[Stephen Compall]

Sorry for prior empty message.

Paul Chiusano <paul.c...@gmail.com> wrote:

>I am not in favor of merging this change, or really any major change
>involving how we handle variance in scalaz, until we have a totally
>methodical writeup of exactly what the problems are with using variance
>annotations, along with a writeup of what has been tried and been shown
>not
>to work, and why. I feel like we are just acting on hearsay and a vague
>impression that "variance is hard, let's go shopping".

I don't think so; https://issues.scala-lang.org/browse/SI-2066 is real, kind variance is backwards approximately half of the time (it doesn't flip in contra-kind-variant positions), Scala 2.11 is if anything *more* schizophrenic about kind variance (wrt bounds see https://issues.scala-lang.org/browse/SI-6169 for lots of fun), and your only hope is bending your mind around polykinds (Pythonically, because scalac won't help you), hoping you got it right, and that you won't run into scalac thinking *only* inconsistent things are consistent & vice versa at the same time.

I'd prefer to think in the more consistent subset of Scala that doesn't have polykinds, until we have a substrate that's worked those issues out.

>trait Functor[F[+_]] { ... }. Any type that is a functor is obviously
>covariant - to go from F[Dog] to F[Animal], just map the identity
>function
>over it! And likewise for types with a contramap - these type
>constructors
>can be made contravariant. Then make related changes to the monad
>transformers and elsewhere. I just think something is really wrong if
>we
>end up having to make an obviously covariant type like IO invariant.

Yes, but I propose that Scala's implementation of variance is the thing that is really wrong, and it must be fixed there before we can safely use it here.

>not
>to make things invariant, but to just give things the correct types,
>with
>LUBs and/or moving things to a FooOps class in the companion object,
>like
>Miles suggests. That approach works out great and I've used it plenty.

I'm in favor of Miles's suggestion, if only because I really dislike Scala 2.10 Option#fold.

>If
>you put the implicit in the companion object, you don't even need an
>explicit import and users of the class can't even 'tell' what's a
>native
>function and what's a pimped function.
>
>I'd like to see this worked through in detail, for all of scalaz. It's
>obviously a breaking change, but it seems like The Right Thing. And if
>this
>doesn't work out for some reason, I want to understand why.

Obviously, I'm loath to sit around the bug tracker, if only because I've experienced things like https://issues.scala-lang.org/browse/SI-6260 too often. I'm happy to talk about cataloguing and formalizing more of these issues. Much of it's a tarpit, though, considering e.g. https://issues.scala-lang.org/browse/SI-7318 is not a bug (there seems to be a dichotomy here regarding variance Dan Doel understands better than I).

Anyway, I'd rather see work towards values over universally quantified type, Haskell-style, than further efforts towards fixing kind variance in scalac.

--
Stephen Compall

If anyone in the MSA is online, you should watch this flythrough.

[Lars Hupel]

> Can you elaborate a bit on the sort of code which used to compile but which
> now will not do so?

There are a two indications, which when combined make it likely that
your code will break:

1) Use of `Free`, `IO`, `Trampoline` and related constructs, or monad
transformers.
2) Use of ADTs without smart constructors or with variance.

While I think the first indication is clear, let me elaborate on the
second one.

A somewhat "daily" occurrence of a related problem:

list.foldLeft(Nil)(...)

where `Nil.type` gets inferred as return type of your fold. Same thing
will happen if you have, say

IO { ... Nil }

then that's an `IO[Nil.type]` which, due to lack of variance in `IO`,
not be automatically up-casted to `IO[List[Whatever]]`. The fix is the
same as in the `foldLeft` example:

list.foldLeft[List[Int]](Nil)(...)
list.foldLeft(Nil: List[Int])(...)
list.foldLeft(List.empty[Int])(...)

Another example: assume you have an `OptionT[List, Left[String,
Nothing]]`. Now, you can write:

value: Option[List, Either[String, Int]]

that's not possible any more. Instead, you'd need [*]:

value.map(x => x: Either[String, Int])

When using scalaz, it's very likely that you use things like

3.some
"foo".left[Int]

already, so in these cases you won't notice a different.

The final example is when you define your own data types with variance,
as already outlined in my original mail:

trait Foo[+A] {

def frobnicate: OptionT[List, A] = ...
}

As I said, there are multiple strategies to solve that, but I completely
forgot number 3 which Miles added.

Does that help?

> I really don't think that scalaz should be making other major changes so
> soon after the v7 upgrade pain. If it's source-compatible (or trivial to
> modify), fine, otherwise, please no.

I'm completely with you on that point. The first measure in that
direction is, as you know, binary compatibility in the 7.0.x series. In
the 7.1.x series, I plan to introduce some (non-breaking) changes which
will improve the bincompat story even more.

About source compatibility: We try to keep the list of breaking changes
at a minimum, as you can see here:
<https://github.com/scalaz/scalaz/wiki/7.1.0-M1#incompatible-changes>.
We're at least going to have one deprecation cycle if possible.

Now, about source compatibility when there is no way for a deprecation
cycle (as it is here in the case of variance). The preceding pull
request [#328] doesn't break anything, so that's good.

Of course, we can discuss whether we should postpone this to 7.2.
However, we *need* to do something about it.


[#328]: https://github.com/scalaz/scalaz/pull/328

[*] I guess we could add a function to `FunctorOps`:

def up[B >: A]: F[B] = self.map(x => x: B)

Then it'd look like:

value.up[Either[String, Int]]

[Lars Hupel]

> Change Functor, Applicative, etc, to take a covariant type constructor -
> trait Functor[F[+_]] { ... }. Any type that is a functor is obviously
> covariant - to go from F[Dog] to F[Animal], just map the identity function
> over it! And likewise for types with a contramap - these type constructors
> can be made contravariant. Then make related changes to the monad
> transformers and elsewhere. I just think something is really wrong if we
> end up having to make an obviously covariant type like IO invariant.

We don't have to. It is still possible to make IO covariant. It's just
not that way in that patch, and that's an arbitrary decision.

IMHO, the question boils down to if we want to treat "is covariant" as a
special case of "is a functor". I'd say no, because in scalaz, we
encourage a certain style of programming: encode ADTs as `sealed trait`
with a number of subclasses, and provide "smart" constructors whose
static return type is that of the trait. Using that style, covariance
doesn't buy very much (if anything). For contravariance, the story is
even worse, because it pretty much messes with implicit search, so I
wouldn't ever encourage making things contravariant.

I do think Mark made some good points on the other pull request, maybe
he can summarize them here.

Another point to note is that a declaration like `Functor[F[+_]]` is not
completely "general" wrt to the kind system in Scala; that would be
`Functor[F[+_ >: H <: T], H, T <: H]`? However, I don't think we want to
go down that rabbit hole.

[Chris Marshall]

I followed everything apart from the "use of Free/IO/Trampoline" bit. I do now use these to trampoline access to a central, database-like resource (it's what I'm working on now, in fact). Is this just going to stop working? Will stuff no longer be trampoline-able? Apols if I've the wrong end of the stick, I find it difficult enough to follow when the code is right in front of me

Chris

[Lars Hupel]

> I followed everything apart from the "use of Free/IO/Trampoline" bit. I do
> now use these to trampoline access to a central, database-like resource
> (it's what I'm working on now, in fact). Is this just going to stop
> working? Will stuff no longer be trampoline-able? Apols if I've the wrong
> end of the stick, I find it difficult enough to follow when the code is
> right in front of me

No, trampolines will continue to work. Assume you have a trampolined
integer value i.e. a `Trampoline[Int]`. That piece of code used to work:

def doSomething(x: Trampoline[AnyVal]) = ...

doSomething(... Trampoline[Int] ...)

Now it won't, because `Trampoline` is not covariant anymore. In other
words, you can't just simply cast a `Trampoline[Int]` to a
`Trampoline[AnyVal]` just because `AnyVal` is a supertype of `Int`.
(Sorry if that's a bad example, but I hope you get the gist.)
^
So, in summary, stuff will continue to be trampoline-able. The
underlying structure (`Free`) has even *less* constraints than
previously, so can be used for more things.

[Chris Marshall]

OK, that's cool. My concern, as always, is "how much of my code has just broken, and how capable am I of fixing it?"

[Runar Bjarnason]

The good news is that the fix is really simple. You just map(x => x).

Runar