Why is the PECS principle not applied to Function1?

[bancsy]

http://stackoverflow.com/questions/11272819/scala-why-is-the-pecs-principle-not-applied-to-function1 

In Effective Java, Joshua Bloch discusses the principle of PECS (Producer-Extends, Consumer-Super).

My understanding of this is that to increase API flexibility, the input (a collection that produces) should be made covariant and the output (collection that consumes) should be contravariant.

A function that implements this principle can have the following signature:

private static void func( ArrayList<? extends Object> input, ArrayList<? super Integer> output)

However, in Scala, the Function1 trait has the following signature: 

trait Function1[-T1, +R] extends AnyRef

T1 (the input type) is contravariant while the R (output type) is covariant.

Is my understanding correct? If so, why is PECS not applied in Scala's Function1 trait?

[Gary Pampara]

I'm sure there are reasons, but using java as a benchmark (and
"standards" within java), for scala is definitely not one of them.

[Roland Kuhn]

You’ve got yourself tied into a knot, I think: the “producing” side of Function1 is covariant and its “consuming” side is contravariant, exactly as it needs to be (anything else would be unsound; unfortunately Java is not sound in this sense, so it cannot be used as a guideline). This has not much to do with Java best practices, it is dictated by type theory.

(If you want to learn more, ask yourself which operations you can do with ArrayList<? extends X> and where you can pass this type as an argument; hint: there are some ClassCastExceptions waiting in the bushes, which are made impossibly by the Scala way—declaration site variance as opposed to Java’s “unchecked” use-site variance)

Regards,

Roland

Roland Kuhn
Typesafe – The software stack for applications that scale.
twitter: @rolandkuhn

[Geir Hedemark]

On 2012, Jun 30, at 11:19 AM, Gary Pampara wrote:
>> Is my understanding correct? If so, why is PECS not applied in Scala's
>> Function1 trait?

> I'm sure there are reasons, but using java as a benchmark (and
> "standards" within java), for scala is definitely not one of them.

Hey, come on. This is a valid question even if it comes from a book about java. Joshua Bloch is one of the best library designers alive. Sometimes, people just want to learn.

... or do you seriously propose that we should ditch actors because they originate in a different language? In that case, Scheme just called and wants its closures back.

Geir

[Dave]

I don't know Effective Java and PECS, but it looks like some sort of a
hackish emulation of contravariance (widening) and covariance
(narrowing) with existentials which is awkward (opposite thinking),
verbose and obsolete thing to do. Existentials are not recommended.
Avoid them where you can.

Scala applies LSP (Liskov Substitution Principle) and you can use just
normal universal types.

According LSP recommendations, arguments are INputs (thus consumers)
and if it's a collection they must be contravariant in their type
parameter and return values are OUTputs (thus producers) and if it's a
collection they must be covariant in their type parameter.
Only then you can guarantee typesafety and keep the API extensible at
the same time.


On 30 jun, 10:57, bancsy <lloydcaban...@gmail.com> wrote:
> http://stackoverflow.com/questions/11272819/scala-why-is-the-pecs-pri...

[Tony Morris]

Using Java as the benchmark is one thing. Using a "principle" from
Effective Java is another again. The fact is, this is not a principle at
all, but simply yet another bad idea.

Let's analyse your question acknowledging my dismissal of this
pseudo-principle and hopefully make sense of why a function's argument
is contravariant (? super in Java syntax) and covariant (? extends in
Java syntax) in the return type. Note also that a function's argument is
often called its domain and its return called its codomain.

First, let's start with: what does it mean exactly for a functor to be
covariant? Which functor anyway? In the case of Function1, we are
talking specifically about the functor free in its return type and I
will invent a syntax to denote this with the ? being a free variable:
Function1[T1, ?]. There is valid Scala syntax for this, but it's a bit
hairy, so I will leave it out and go with my invented syntax.

A functor F is covariant if there exists an operation [A, B](A => B) =>
(F[A] => F[B]) for that functor satisfying a couple of laws, which we
will omit for now. Astute Scala users will notice that this is the
signature to the usual map method. So, is Function1[T, ?] a covariant
functor? That is to say, when we replace F with Function1[T, ?], do we
get to where we need to?

That question is equivalent to this question: can there exist a value
with this signature (+laws):

def IsItCovariant[A, B]: (A => B) => Function1[T, A] => Function1[T, B]

The answer is a clear yes -- this operation exists and indeed, is
already implemented in the standard library. It is called "compose" and
is a method on scala.Function1. In fact, as a useful coincidence, there
is *no other possible* method with this signature (some caveats aside)
except for what is commonly called "function composition." As a side
note, given that Scala has special for-comprehension syntax for methods
named map, it is a little annoying that this method is named compose and
not map! I suppose this is not a big deal in the absence of a flatMap
implementation too. I digress, but feel free to "add those methods"
yourself in the usual Scala way.

So, Function1[T, ?] is a covariant functor, because it meets the
definition of covariance -- it also meets the laws too, take my word for
it (happy to expand here if there is distrust or curiosity).

You will notice this function signature: (A => B) => (F[A] => F[B]) is
simply symbols for what is often stated in English:

"If A subclasses B, then F[A] subclasses F[B]." You can use the =>
symbol to denote both "if/then" and a "subclassing" relationship -- they
are equivalent.

Sometimes it is also written like this:
if A <: B then F[A] <: F[B]

or perhaps like this:
(A <: B) => (F[A] <: F[B])

Again, we are just replacing symbols with English -- the concept is the
same -- it is logical implication. Feel free to use your preferred
denotation and communication method, with the caveat that there are
implementation details that might throw it off a bit if you get too
loose with the informalities.

As for contravariance, we have a very similar question. First, what is a
contravariant functor? It is any functor giving rise to this operation:
[A, B](A => B) => F[B] => F[B]

There is the same correspondence with subtype/supertype relationships
and logical implication and all that. Different symbols or loose English
expressions, but it all boils down to the same principle.

Again, we have a couple (exactly 2) laws to satisfy. So now the
question, is Function1[?, R] a contravariant functor? Well, this is just
the same as asking, does this operation exist (+laws):

def IsItContravariant[A, B]: (A => B) => Function1[B, R] => Function1[A, R]

Again, the answer is yes and again, coincidentally, there is only one
possible implementation of this method (and it satisfies our unstated
laws). It is implemented in the Scala standard library as the
scala.Function1#andThen method. Look it up if you like!

Now, if you apply the same reasoning and switch the variance around on
the function's domain/codomain, you will find that you can *not*
implement those methods (and so there is point testing for any laws!).
Try it if you like. That is to say, the functor of a function free in
its domain is contravariant and only contravariant, while free in its
codomain is covariant and only covariant.

Since you seem to be a fan of principled reasoning, I hope this
"mechanical test" for whether a functor is covariant or contravariant
(or perhaps neither, being invariant aka exponential) will help you.
Instead of "PECS principle", let's call it "algebra."

You can apply this test to *any* functor in our category. For example,
suppose the following data structure:
case class ReaderState[R, S, A](run: R => S => (A, S))

Is ReaderState[R, S, ?] covariant, invariant or contravariant? What
about the ReaderState[R, ?, A] or ReaderState[?, S, A] functors? I will
leave these three as reader's exercises, but just apply the mechanical
test (although, you will need those laws to truly get the answer with
total confidence).

As for the laws that I left out, I did this for the purpose of
explanation, not because of intent to deceive or because they are
unimportant, quite the contrary. Only because I didn't think stating the
laws explicitly is necessary to this introductory explanation. If you'd
like to go the next step and explore this subject further, I'd be happy
to do so and we'd have to take a look at those laws -- in fact, an
excellent exercise might be to express these laws in Scala using the
ScalaCheck library (another reader exercise?). These laws are called
"identity law" and "composition law" and apply to both covariant and
contravariant functors if you'd like to search for them and read further.

As always, hope that helps!

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

[Miguel Garcia]

As an aside, there's a succinct review of declaration-site vs. use-site variance in Sec. 1 and 2 of

    Java Wildcards Meet Definition-Site Variance
    John Altidor, Christoph Reichenbach, Yannis Smaragdakis
    ECOOP 2012
    http://people.cs.umass.edu/~yannis/varj-ecoop12.pdf

A well thought out (but way more detailed) analysis of Java wildcards can be found at http://cseweb.ucsd.edu/~rtate/publications/tamewild/


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[Tony Morris]

On 30/06/12 20:49, Tony Morris wrote:
> As for contravariance, we have a very similar question. First, what is a
> contravariant functor? It is any functor giving rise to this operation:
> [A, B](A => B) => F[B] => F[B]

Sorry, typo.

The correct signature for contravariance is:
[A, B](A => B) => F[B] => F[A]

PS: I sometimes wonder if spell-correctors of the future will pick that
up, "you just wrote a function signature that is not very useful. Did
you mean to write this instead...?"

[Andreas Joseph Krogh]

I won't be surprised if IntelliJ will provide this in the future:-)
Although they call it "intentions".

--
Andreas Joseph Krogh<and...@officenet.no> - mob: +47 909 56 963
Senior Software Developer / CEO - OfficeNet AS - http://www.officenet.no
Public key: http://home.officenet.no/~andreak/public_key.asc

[Chris Marshall]

You also got compose and andThen the wrong way round. g(f(x)) is  (f andThen g)(x) or (g compose f)(x). Hence

 - andThen is "map"

 - compose is "contra-map"

Chris

> Date: Sat, 30 Jun 2012 21:02:02 +1000
> From: tonym...@gmail.com
> To: scala...@googlegroups.com
> Subject: Re: [scala-user] Why is the PECS principle not applied to Function1?

[Daniel Sobral]

Joshua is correct, and so is Scala. In fact, Scala mandates this rule, so you don't need to worry about it. Java, because it doesn't have variance annotations and has to make do with existentials at the call site, needs them to guide the programmers as to the correct design.

What is wrong is your association of input with producer and output with consumer. An input is what is consumed, while an output is what is produced.

On the other hand, Scala has variance annotations at the definition site, while java has existentials at the call site. The output of the call is the input of the definition, and vice versa. So perhaps, you are thinking call site instead of definition site.

[Vlad Patryshev]

T is producer, R is consumer; and whatever "Effective Java" says may
be just a political enforcement of variance that is absent in Java.
Anyway, Java rituals are meaningless in Scala world.

Thanks,
-Vlad

[Tony Morris]

I'm pretty sure that compose is a method on A => B taking an argument of
the type X => A and return a value of the type X => B, hence
compose/map: (A => B) => (X => A) => (X => B).

[Stephen Compall]

On Jun 30, 2012, at 7:31 PM, Tony Morris <tonym...@gmail.com> wrote:
> compose/map: (A => B) => (X => A) => (X => B).

Except in Scala, the functor is the first, not second argument. This is irrelevant for function1, naturally, for which it is no use favoring one map/contra interpretation over the other, but matters for the collection analogy:

F[A,B] => (X => A) => F[X,B]

--
Stephen Compall
Greetings from sunny Appleton!

[Chris Marshall]

A covariant functor, M's map method looks like this:

def fmap(f: M[A], fn: A => B): M[B]

I think you would agree that the implementation for M = X => A (for some fixed type X) is as follows:

f andThen fn

In the same way that if M = List or Option it would be

f map fn

I'm pretty sure I'm right (given that I learnt this from scalaz in the first place). I agree with how you describe "compose" below but it is not the covariant functor's "map" method

Chris

> Date: Sun, 1 Jul 2012 09:31:58 +1000
> From: tonym...@gmail.com
> To: oxbow...@hotmail.com
> CC: scala...@googlegroups.com

> Subject: Re: [scala-user] Why is the PECS principle not applied to Function1?
>