Structural typing without reflection

On Friday June 25 2010, Nils Kilden-Pedersen wrote:
> I've now been bitten by this long standing reflection bug:
>
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4071957
>
> This brings me to once again wonder why structural typing cannot be
> done without reflection. To the best of my knowledge, structural
> types are type safe, so the method signatures MUST be validated at
> compile time, which also means that a compiler generated proxy should
> be an option rather than relying on runtime reflection.
>
> Or am I missing some feature of structural typing that would make
> this unfeasible?

The compiler knows that the class feature being accessed is present, but
there is no single class or interface statically known that supplies
that feature. It's known _that_ the feature is present, but not which
class or interface defines it (there may be many). Hence reflection is
required to resolve that unknown at run time.

Randall Schulz

On Friday 25 June 2010, Randall R Schulz said:

> The compiler knows that the class feature being accessed is present, but
> there is no single class or interface statically known that supplies
> that feature. It's known _that_ the feature is present, but not which
> class or interface defines it (there may be many). Hence reflection is
> required to resolve that unknown at run time.

Would this be able to take advantage of invokedynamic, as that becomes
more available?

David

On Friday June 25 2010, David Brown wrote:
> On Friday 25 June 2010, Randall R Schulz said:
> > The compiler knows that the class feature being accessed is
> > present, but there is no single class or interface statically known
> > that supplies that feature. It's known _that_ the feature is
> > present, but not which class or interface defines it (there may be
> > many). Hence reflection is required to resolve that unknown at run
> > time.
>
> Would this be able to take advantage of invokedynamic, as that
> becomes more available?
>
> David

I've heard talk about that, but I don't know enough to say, myself.

Randall Schulz

On Fri, Jun 25, 2010 at 10:37 PM, Randall R Schulz <rschulz [at] sonic [dot] net> wrote:

The compiler knows that the class feature being accessed is present, but
there is no single class or interface statically known that supplies
that feature.

So let the compiler make an interface to match the structural type. And then have the compiler generate the proxy implementations of that interface for every class that matches the structural type.

On Saturday June 26 2010, Nils Kilden-Pedersen wrote:
> On Fri, Jun 25, 2010 at 10:37 PM, Randall R Schulz
wrote:
> > The compiler knows that the class feature being accessed is
> > present, but there is no single class or interface statically known
> > that supplies that feature.
>
> So let the compiler make an interface to match the structural type.
> And then have the compiler generate the proxy implementations of that
> interface for every class that matches the structural type.

I don't believe that's even close to feasible.

Where does it mix them in (to which classes)? How does it find all the
classes that might appear at run time that conform to the structural
types extant in a given (dynamically linked) program in order to
rewrite them to bear that interface? When does it do this?

Randall Schulz

Randall R Schulz wrote:

> I don't believe that's even close to feasible.
>
> Where does it mix them in (to which classes)? How does it find all the
> classes that might appear at run time that conform to the structural
> types extant in a given (dynamically linked) program in order to
> rewrite them to bear that interface? When does it do this?

http://blogs.sun.com/jrose/entry/interface_injection_in_the_vm

On Sat, Jun 26, 2010 at 8:35 AM, Randall R Schulz <rschulz [at] sonic [dot] net> wrote:

Where does it mix them in (to which classes)? How does it find all the
classes that might appear at run time that conform to the structural
types extant in a given (dynamically linked) program in order to
rewrite them to bear that interface? When does it do this?

type Foo = { def hello() }

Compiler would generate this anonymous interface:
interface Foo$anon$ { def hello() }

and
def foo(f: Foo) {
  f.hello()
}

would be compiled to
def foo(f: Foo$anon$) {
  f.hello()
}

Now, using this structurally matching class:
class Bar {
  def hello() = println("Quack")
}

when compiling against this:
val bar = new Bar
foo(bar)

would generate this proxy
class Foo$Bar$anon$ (b: Bar) extends Foo$anon$ {
  def hello() = b.hello()
}

and the call turned into this
val bar = new Bar
foo(new Foo$Bar$anon$(bar))

It's entirely possible I'm missing some feature of structural types that I'm unaware of, but this seems very feasible to me.

Nils Kilden-Pedersen wrote:
> It's entirely possible I'm missing some feature of structural types that
> I'm unaware of, but this seems very feasible to me.

def baz(f:Foo) = assert(f.isInstanceOf[Bar])

oops.

On Sat, Jun 26, 2010 at 11:41 AM, Vladimir Kirichenko <vladimir [dot] kirichenko [at] gmail [dot] com> wrote:

Nils Kilden-Pedersen wrote:
> It's entirely possible I'm missing some feature of structural types that
> I'm unaware of, but this seems very feasible to me.

def baz(f:Foo) = assert(f.isInstanceOf[Bar])

oops.

Fair enough, although that's a, in this context, particularly weird use case.

Nils Kilden-Pedersen wrote:
> def baz(f:Foo) = assert(f.isInstanceOf[Bar])
>
> oops.
> Fair enough, although that's a, in this context, particularly weird use
> case.

Just trying to show that messing with instances is not (actually it's
very bad) thing. There will be very mysterious thing if passing the
object as a parameter could replace the instance of the object just
because of structural check. The worst thing because of this could be:

def f[T <: {...}](x: T) = x

val a = ...
val b = f(a);
assert(b == a); //oops

On Sat, Jun 26, 2010 at 12:31 PM, Vladimir Kirichenko <vladimir [dot] kirichenko [at] gmail [dot] com> wrote:

Just trying to show that messing with instances is not (actually it's
very bad) thing. There will be very mysterious thing if passing the
object as a parameter could replace the instance of the object just
because of structural check.

No, I completely agree. I just don't think one would normally do this, so I wasn't really considering that case. But it's true, it makes my solution infeasible.

Hello.

In the following paper:

http://infoscience.epfl.ch/record/138931/files/2009_structural.pdf

I compare the performance of Scala's reflective implementation of structural types and the implementation of Whiteoak, a language with structural types compiled to the JVM using dynamically generated adapter classes.

The summary of this paper can be read as a discussion on why Scala implements structural types using reflection and not by generating adapter classes. In short:

- generating adapter classes is faster in tight loops;
- when the cost of structural dispatch is distributed over many call sites, it is unclear whether generating adapter classes is faster than good reflection;
- implementing structural types by generating adapter classes is much more complex and creates a dependency on a code generation library for all programs.

Cheers,
Gilles.

>>> The compiler knows that the class feature being accessed is
>>> present, but there is no single class or interface statically known
>>> that supplies that feature.
>>
>> So let the compiler make an interface to match the structural type.
>> And then have the compiler generate the proxy implementations of that
>> interface for every class that matches the structural type.
>
> I don't believe that's even close to feasible.
>
> Where does it mix them in (to which classes)? How does it find all the
> classes that might appear at run time that conform to the structural
> types extant in a given (dynamically linked) program in order to
> rewrite them to bear that interface? When does it do this?