Scala’s existential types

What makes you think they are different?

On Tue, Jun 23, 2009 at 5:19 AM, christopher marshall <oxbow_lakes [at] hotmail [dot] com> wrote:

I've also asked this question: http://stackoverflow.com/questions/1031042/scalas-existential-types

Can someone tell me what is the difference between Scala's existential types and Java's wildcard, prefereably with some illustrative example?

In everything I've seen so far, they seem to be pretty equivalent.

Refs: http://www.artima.com/scalazine/articles/scalas_type_system.html, http://scalada.blogspot.com/2008/01/existential-types.html

I hope no one minds my cross-referencing questions. StackOverflow is really a fantastic community resource for this kind of thing. It would be really great if we could build up the scala community's presence on there so that e.g. Java developers who are already on there can get their Scala answers too.

Chris

View your Twitter and Flickr updates from one place – Learn more!

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

The original Java wildcard types (as described in the ECOOP paper by
Igarashi and Viroli) were indeed just shorthands for existential
types. I am told and I have read in the FOOL '05 paper on Wild FJ that
the final version of wildcards has some subtle differences with
existential types. I would not know exactly in what sense (their
formalism is too far removed from classical existential types to be
able to pinpoint the difference), but maybe a careful read of the Wild
FJ paper would shed some light on it.

Cheers

On Tuesday June 23 2009, christopher marshall wrote:
> I've also asked this question:
> http://stackoverflow.com/questions/1031042/scalas-existential-types
> Can someone tell me what is the difference between Scala's
> existential types and Java's wildcard, prefereably with some
> illustrative example?

Existential types were introduced so that Scala's type system could
capture Java's wildcards. This is made clear in the Artima interview
with Martin Odersky that you referenced [1].

"Bill Venners: Can you give a specific example?

Martin Odersky: Take Scala lists as an example. I want to be able to
describe the return type of the method, head, which returns the first
element (the "head") of the list. On the VM level, it is a List[T]
forSome { type T }. We don't know what T is, but head returns a T. The
theory of existential types tells us that is a T for some type T, which
is equivalent to the root type, Object. So we get this back from the
head method. Thus in Scala, when we know something we can eliminate
these existential qualifications. When we don't know something, we
leave them in, and the theory of existential types helps us there. "

"Bill Venners: Would you have added existential types if you didn't need
to worry about the Java compatibility concerns of wildcards, raw types,
and erasure. If Java had reified types and no raw types or wildcards,
would Scala have existential types?

Martin Odersky: If Java had reified types and no raw types or wildcards,
I don't think we would have that much use for existential types and I
doubt they would be in Scala. "

Are these not sufficient to answer your questions?

[1] http://www.artima.com/scalazine/articles/scalas_type_system.html

> ...

Randall Schulz

.hmmessage P { margin:0px; padding:0px } body.hmmessage { font-size: 10pt; font-family:Verdana } The link I posted was Martin saying "The original [Java] wildcard design ... was inspired by existential types. In fact the original paper had an encoding in existential types. But then when the actual final design came out in Java, this connection got lost a little bit"
I recall reading that a "positive" about Scala (in the days before existential types were added, presumably) was that it "didn't have wildcard types". Admittedly I can't remember where I read this but I'm pretty sure I did. I wanted to know what, if wildcards were so bad, why Scala's existential types appear to be identical.

From: dcsobral [at] gmail [dot] com
Date: Tue, 23 Jun 2009 11:12:45 -0300
Subject: [scala-user] Re: [scala-user] Scala’s existential types
To: oxbow_lakes [at] hotmail [dot] com
CC: scala-user [at] listes [dot] epfl [dot] ch

What makes you think they are different?

On Tue, Jun 23, 2009 at 5:19 AM, christopher marshall <oxbow_lakes [at] hotmail [dot] com> wrote:

I've also asked this question: http://stackoverflow.com/questions/1031042/scalas-existential-types

Can someone tell me what is the difference between Scala's existential types and Java's wildcard, prefereably with some illustrative example?

In everything I've seen so far, they seem to be pretty equivalent.

Refs: http://www.artima.com/scalazine/articles/scalas_type_system.html, http://scalada.blogspot.com/2008/01/existential-types.html

I hope no one minds my cross-referencing questions. StackOverflow is really a fantastic community resource for this kind of thing. It would be really great if we could build up the scala community's presence on there so that e.g. Java developers who are already on there can get their Scala answers too.

Chris

View your Twitter and Flickr updates from one place – Learn more!

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

Beyond Hotmail — see what else you can do with Windows Live. Find out more.

On Tue, Jun 23, 2009 at 05:54:29PM +0000, christopher marshall wrote:
> I recall reading that a "positive" about Scala (in the days before
> existential types were added, presumably) was that it "didn't have
> wildcard types". Admittedly I can't remember where I read this but I'm
> pretty sure I did. I wanted to know what, if wildcards were so bad,
> why Scala's existential types appear to be identical.

That paragraph is misguided for at least two reasons: I doubt you read
that (it is much more likely the cited advantage was that it doesn't
have RAW types, which are completely different) and the motivation
behind adding existential types to scala was precisely to interoperate
with java. So don't go blaming the victim here.

Scala does have wildcard types, but doesn't need to use them nearly as often as Java does. Why? Because Scala allows co-/contra-variance annotations on types. This lets the library designer worry about the types, simplifying the more common programming tasks.

Let's take the example from the first Google result for "java wildcards": http://java.sun.com/docs/books/tutorial/extra/generics/wildcards.html

I'm going to skip the first example (printing an arbitrary collection) because it's better solved by using type parameters (generics).

The second example is about printing shapes to a canvas. Consider:

  abstract class Shape {
    def draw(c: Canvas): Unit
  }

  case class Circle(x: Int, y: Int, radius: Int) extends Shape {
    def draw(c: Canvas): Unit = ()
  }

  case class Rectangle(x: Int, y: Int, width: Int, height: Int) extends Shape {
    def draw(c: Canvas): Unit = ()
  }

Now what if we wanted to have a "drawAll" method on Canvas which takes a List of Shapes? In Java, we'd need to use existentials (wildcards), like so:

  class Canvas {
    def draw(s: Shape): Unit = s.draw(this)
    def drawAll(shapes: List[_ <: Shape]): Unit = shapes.foreach(_ draw this)
  }

However, Scala's List has been annotated by the library designer to be covariant. This means that since Circle and Rectangle are Shapes, then Lists of Circles and Lists of Rectangles are also Lists of Shapes. That means the "intuitive" definition for drawAll, which doesn't work in Java, does work in Scala:

    def drawAll(shapes: List[Shape]): Unit = shapes.foreach(_ draw this)

So, yes, Scala does have existential types. They're useful when you're dealing with java.util.List which is not (and cannot be) covariant. When you're using the covariant scala.List, however, existential types are almost never necessary.

--j

On Tue, Jun 23, 2009 at 10:54 AM, christopher marshall <oxbow_lakes [at] hotmail [dot] com> wrote:

The link I posted was Martin saying "The original [Java] wildcard design ... was inspired by existential types. In fact the original paper had an encoding in existential types. But then when the actual final design came out in Java, this connection got lost a little bit"
I recall reading that a "positive" about Scala (in the days before existential types were added, presumably) was that it "didn't have wildcard types". Admittedly I can't remember where I read this but I'm pretty sure I did. I wanted to know what, if wildcards were so bad, why Scala's existential types appear to be identical.

From: dcsobral [at] gmail [dot] com
Date: Tue, 23 Jun 2009 11:12:45 -0300
Subject: [scala-user] Re: [scala-user] Scala’s existential types
To: oxbow_lakes [at] hotmail [dot] com
CC: scala-user [at] listes [dot] epfl [dot] ch

What makes you think they are different?

On Tue, Jun 23, 2009 at 5:19 AM, christopher marshall <oxbow_lakes [at] hotmail [dot] com> wrote:

I've also asked this question: http://stackoverflow.com/questions/1031042/scalas-existential-types

Can someone tell me what is the difference between Scala's existential types and Java's wildcard, prefereably with some illustrative example?

In everything I've seen so far, they seem to be pretty equivalent.

Refs: http://www.artima.com/scalazine/articles/scalas_type_system.html, http://scalada.blogspot.com/2008/01/existential-types.html

I hope no one minds my cross-referencing questions. StackOverflow is really a fantastic community resource for this kind of thing. It would be really great if we could build up the scala community's presence on there so that e.g. Java developers who are already on there can get their Scala answers too.

Chris

View your Twitter and Flickr updates from one place – Learn more!

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

Beyond Hotmail — see what else you can do with Windows Live. Find out more.

.hmmessage P { margin:0px; padding:0px } body.hmmessage { font-size: 10pt; font-family:Verdana } I'm not blaming anyone - I merely wondered whether I had perhaps misunderstood what an existential type was. You are perhaps correct in that I am misremembering a paragraph about how Scala's type system compared with Java's, which would likely have mentioned wildcards, raw types etc.   

> Date: Tue, 23 Jun 2009 11:11:26 -0700
> From: paulp [at] improving [dot] org
> To: oxbow_lakes [at] hotmail [dot] com
> CC: dcsobral [at] gmail [dot] com; scala-user [at] listes [dot] epfl [dot] ch
> Subject: Re: [scala-user] RE: [scala-user] Re: [scala-user] Scala’s existential types
>
> On Tue, Jun 23, 2009 at 05:54:29PM +0000, christopher marshall wrote:
> > I recall reading that a "positive" about Scala (in the days before
> > existential types were added, presumably) was that it "didn't have
> > wildcard types". Admittedly I can't remember where I read this but I'm
> > pretty sure I did. I wanted to know what, if wildcards were so bad,
> > why Scala's existential types appear to be identical.
>
> That paragraph is misguided for at least two reasons: I doubt you read
> that (it is much more likely the cited advantage was that it doesn't
> have RAW types, which are completely different) and the motivation
> behind adding existential types to scala was precisely to interoperate
> with java. So don't go blaming the victim here.
>
> --
> Paul Phillips | We must respect the other fellow's religion, but only
> Caged Spirit | in the sense and to the extent that we respect his
> Empiricist | theory that his wife is beautiful and his children smart.
> all hip pupils! | -- H. L. Mencken

Beyond Hotmail — see what else you can do with Windows Live. Find out more.