[scala] Structural types with generic type question

[fakechris]

Hi,
  I try to define structural types with generic type  in function parameter. But got this error:

 
scala> abstract class Test2{
     |  def test[T]( f: {def id(i:T):int})
     | }
<console>:5: error: Parameter type in structural refinement may not refer to abs
tract type defined outside that same refinement
        def test[T]( f: {def id(i:T):int})
                                  ^

  However, generic type  in return position will be ok

scala> abstract class Test1{
     |  def test[T]( f: {def id():T})
     | }
defined class Test1

Any reason?
Thanks

Chris Song

[Gilles Dubochet-2]

Hello list.

> I try to define structural types with abstract datatype in function
> parameter. ... Any reason?

I have heard about two questions concerning the structural typing
extension of Scala 2.6 lately, and I would like to answer them here.
 1. Why did we change Scala's native values (“int”, etc.) boxing scheme
to Java's (“java.lang.Integer”).
 2. Why is the restriction on parameters for structurally defined
methods (“Parameter type in structural refinement may not refer
to abstract type defined outside that same refinement”) required.

Before I can answer these two questions, I need to speak about the
implementation of structural types.

The JVM's type system is very basic (and corresponds to Java 1.4). That
means that many types that can be represented in Scala cannot be
represented in the VM. Path dependant types (“x.y.A”), singleton types
(“a.type”), compound types (“A with B”) or abstract types are all types
that cannot be represented in the JVM's type system. 

To be able to compile to JVM bytecode, the Scala compilers changes the
Scala types of the program to their “erasure” (see section 3.6 of the
reference). Erased types can be represented in the VM's type system and
define a type discipline on the program that is equivalent to that of
the program typed with Scala types (saving some casts), although less
precise. As a side note, the fact that types are erased in the VM
explains why operations on the dynamic representation of types (pattern
matching on types) are very restricted with respect to Scala's type
system.

Until now all type constructs in Scala could be erased in some way.
This isn't true for structural types. The simple structural type “{ def
x: Int }” can't be erased to “Object” as the VM would not allow
accessing the “x” field. Using an interface “interface X { int x{}; }”
as the erased type won't work either because any instance bound by a
value of this type would have to implement that interface which cannot
be done in presence of separate compilation. Indeed (bear with me) any
class that contains a member of the same name than a member defined in
a structural type anywhere would have to implement the corresponding
interface. Unfortunately this class may be defined even before the
structural type is known to exist.

Instead, any reference to a structurally defined member is implemented
as a reflective call, completely bypassing the VM's type system. For
example “def f(p: { def x(q: Int): Int }) = p.x(4)” will be rewritten
to something like:
  def f(p: Object) = p.getClass.getMethod("x", Array(Int)).invoke(p, Array(4))


And now the answers. 

1. “invoke” will use boxed (“java.lang.Integer”) values whenever the
invoked method uses native values (“int”). That means that the above
call must really look like “...invoke(p, Array(new
java.lang.Integer(4))).intValue”.

Integer values in a Scala program are already often boxed (to allow the
“Any” type) and it would be wasteful to unbox them from Scala's own
boxing scheme to rebox them immediately as java.lang.Integer.

Worst still, when a reflective call has the “Any” return type,
what should be done when a java.lang.Integer is returned? The called
method may either be returning an “int” (in which case it should be
unboxed and reboxed as a Scala box) or it may be returning a
java.lang.Integer that should be left untouched.

Instead we decided to change Scala's own boxing scheme to Java's. The
two previous problems then simply disappear. Some performance-related
optimisations we had with Scala's boxing scheme (pre-calculate the
boxed form of the most common numbers) were easy to use with Java
boxing too. In the end, using Java boxing was even a bit faster than
our own scheme.


2. “getMethod”'s second parameter is an array with the types of the
parameters of the (structurally defined)  method to lookup — for
selecting which method to get when the name is overloaded. This is the
one place where exact, static types are needed in the process of
translating a structural member call. Usually, exploitable static types
for a method's parameter are provided with the structural type
definition. In the example above, the parameter type of “x” is known to
be “Int”, which allows looking it up.

Parameter types defined as abstract types where the abstract type is
defined inside the scope of the structural refinement are no problem
either:
  def f(p: { def x[T](t: T): Int }) = p.x[Int](4)
In this example we know that any instance passed to “f” as “p” will
define “x[T](t: T)” which is necessarily erased to  “x(t: Object)”. The
lookup is then correctly done on the erased type:
  def f(p: Object) = p.getClass.getMethod("x", Array(Object)).invoke(p,
Array(new java.lang.Integer(4)))

But if an abstract type from outside the structural refinement's scope
is used to define a parameter of a structural method, everything breaks:
  def f[T](p: { def x(t: T): Int }, t: T) = p.x(t)
When “f” is called, “T” can be instantiated to any type, for example:
  f[Int]({ def x(t: Int) = t }, 4)
  f[Any]({ def x(t: Any) = 5 }, 4)
The lookup for the first case would have to be “getMethod("x",
Array(int))” and for the second “getMethod("x", Array(Object))”, and
there is no way to know which one to generate in the body of
“f”: “p.x(t)”.

To allow defining a unique “getMethod” call inside “f”'s body for
any instantiation of “T” would require any object passed to “f” as the
“p” parameter to have the type of “t” erased to “Any”.  This would be a
transformation where the type of a class' members depend on how
instances of this class are used in the program. And this is something
we definitely don't want to do (and can't be done with separate
compilation).

Alternatively, if Scala supported run-time types one could use them to
solve this problem. Maybe one day ...

But for now, using abstract types for structural method's parameter
types is simply forbidden.


Sincerely,
Gilles.

[James Iry]

I'm curious as to what the holes would be if instead of reflection,
structural types caused a synthetic class or trait to be created at compile
time and every call to a structural typed method would cause the compiler to
create a new anonymous adapter (or maybe even sometimes reuse an adapter
class that was previously created).  Hmmm, actually I can see that identity
is a potential problem...but still, here's the notion...

I apologize for syntactic errors, I didn't run any of this through a
compiler:

type Duck = {
              def quack()
            }

def makeDuckQuack(Duck duck) =
  duck.quack()

def main(Array[String] args) =
  makeDuckQuack(new Mallard)

Gets translated into something along the lines of

class Duck = {
  abstract def quack()
}

def makeDuckQuack(Duck duck) =
  duck.quack()

def main(Array[String] args) = {
  $anonM = new Mallard
  $anonDuck = new Duck {
     def quack = $anonM.quack()
  }
  makeDuckQuack($anonDuck)
}


-----Original Message-----
From: news [mailto:[hidden email]] On Behalf Of Gilles Dubochet
Sent: Thursday, August 23, 2007 7:08 AM
To: [hidden email]
Subject: [scala] Re: Structural types with ADT question


Hello list.

> I try to define structural types with abstract datatype in function
> parameter. ... Any reason?

I have heard about two questions concerning the structural typing
extension of Scala 2.6 lately, and I would like to answer them here.
 1. Why did we change Scala's native values (“int”, etc.) boxing scheme
to Java's (“java.lang.Integer”).
 2. Why is the restriction on parameters for structurally defined
methods (“Parameter type in structural refinement may not refer
to abstract type defined outside that same refinement”) required.

Before I can answer these two questions, I need to speak about the
implementation of structural types.

The JVM's type system is very basic (and corresponds to Java 1.4). That
means that many types that can be represented in Scala cannot be
represented in the VM. Path dependant types (“x.y.A”), singleton types
(“a.type”), compound types (“A with B”) or abstract types are all types
that cannot be represented in the JVM's type system. 

To be able to compile to JVM bytecode, the Scala compilers changes the
Scala types of the program to their “erasure” (see section 3.6 of the
reference). Erased types can be represented in the VM's type system and
define a type discipline on the program that is equivalent to that of
the program typed with Scala types (saving some casts), although less
precise. As a side note, the fact that types are erased in the VM
explains why operations on the dynamic representation of types (pattern
matching on types) are very restricted with respect to Scala's type
system.

Until now all type constructs in Scala could be erased in some way.
This isn't true for structural types. The simple structural type “{ def
x: Int }” can't be erased to “Object” as the VM would not allow
accessing the “x” field. Using an interface “interface X { int x{}; }”
as the erased type won't work either because any instance bound by a
value of this type would have to implement that interface which cannot
be done in presence of separate compilation. Indeed (bear with me) any
class that contains a member of the same name than a member defined in
a structural type anywhere would have to implement the corresponding
interface. Unfortunately this class may be defined even before the
structural type is known to exist.

Instead, any reference to a structurally defined member is implemented
as a reflective call, completely bypassing the VM's type system. For
example “def f(p: { def x(q: Int): Int }) = p.x(4)” will be rewritten
to something like:
  def f(p: Object) = p.getClass.getMethod("x", Array(Int)).invoke(p,
Array(4))


And now the answers. 

1. “invoke” will use boxed (“java.lang.Integer”) values whenever the
invoked method uses native values (“int”). That means that the above
call must really look like “...invoke(p, Array(new
java.lang.Integer(4))).intValue”.

Integer values in a Scala program are already often boxed (to allow the
“Any” type) and it would be wasteful to unbox them from Scala's own
boxing scheme to rebox them immediately as java.lang.Integer.

Worst still, when a reflective call has the “Any” return type,
what should be done when a java.lang.Integer is returned? The called
method may either be returning an “int” (in which case it should be
unboxed and reboxed as a Scala box) or it may be returning a
java.lang.Integer that should be left untouched.

Instead we decided to change Scala's own boxing scheme to Java's. The
two previous problems then simply disappear. Some performance-related
optimisations we had with Scala's boxing scheme (pre-calculate the
boxed form of the most common numbers) were easy to use with Java
boxing too. In the end, using Java boxing was even a bit faster than
our own scheme.


2. “getMethod”'s second parameter is an array with the types of the
parameters of the (structurally defined)  method to lookup — for
selecting which method to get when the name is overloaded. This is the
one place where exact, static types are needed in the process of
translating a structural member call. Usually, exploitable static types
for a method's parameter are provided with the structural type
definition. In the example above, the parameter type of “x” is known to
be “Int”, which allows looking it up.

Parameter types defined as abstract types where the abstract type is
defined inside the scope of the structural refinement are no problem
either:
  def f(p: { def x[T](t: T): Int }) = p.x[Int](4)
In this example we know that any instance passed to “f” as “p” will
define “x[T](t: T)” which is necessarily erased to  “x(t: Object)”. The
lookup is then correctly done on the erased type:
  def f(p: Object) = p.getClass.getMethod("x", Array(Object)).invoke(p,
Array(new java.lang.Integer(4)))

But if an abstract type from outside the structural refinement's scope
is used to define a parameter of a structural method, everything breaks:
  def f[T](p: { def x(t: T): Int }, t: T) = p.x(t)
When “f” is called, “T” can be instantiated to any type, for example:
  f[Int]({ def x(t: Int) = t }, 4)
  f[Any]({ def x(t: Any) = 5 }, 4)
The lookup for the first case would have to be “getMethod("x",
Array(int))” and for the second “getMethod("x", Array(Object))”, and
there is no way to know which one to generate in the body of
“f”: “p.x(t)”.

To allow defining a unique “getMethod” call inside “f”'s body for
any instantiation of “T” would require any object passed to “f” as the
“p” parameter to have the type of “t” erased to “Any”.  This would be a
transformation where the type of a class' members depend on how
instances of this class are used in the program. And this is something
we definitely don't want to do (and can't be done with separate
compilation).

Alternatively, if Scala supported run-time types one could use them to
solve this problem. Maybe one day ...

But for now, using abstract types for structural method's parameter
types is simply forbidden.


Sincerely,
Gilles.

No virus found in this incoming message.
Checked by AVG Free Edition.
Version: 7.5.484 / Virus Database: 269.12.2/967 - Release Date: 8/22/2007
6:51 PM
 

No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.5.484 / Virus Database: 269.12.2/967 - Release Date: 8/22/2007
6:51 PM