- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
Size of standard library and possible tricks to reduce its size
Sat, 2011-12-03, 06:07
#52
Re: Re: Size of standard library and possible tricks to reduce
On Fri, Dec 2, 2011 at 11:27 PM, Pavel Pavlov wrote:
> Loosing weight for Traversable requires creation of class
> TraversableLike$AC, which I just defined as "abstract class
> TraversableLike$AC[+T, +R] extends AnyRef with TraversableLike[T, R]". This
> version of TraversableLike$AC contain now 98 forwarders, class size is 22632
> bytes, so all fat from Traversable$AC is moved here.
That's the issue here: There's a much more complicated hierarchy than
just one or two traits. It's pretty extensive inside scala.collection,
and can result in some pretty deep inheritance trees for the final
concrete classes.
So I'm not so sure that it's a clear win. It it could even be
detrimental (to actual runtime overhead) to create abstract class
layers for everything, including traits like TraversableLike which are
never meant to be inherited directly.
Sat, 2011-12-03, 07:27
#53
Re: Re: Size of standard library and possible tricks to reduce
On Fri, Dec 2, 2011 at 11:27 PM, Pavel Pavlov <pavel.e...@gmail.com> wrote:
In this case hovewer, we already have deep inheritance hierarchy through interfaces at JVM level, and adding forwarder classes won't make class inheritance height deeper than current interface inheritance height.
As I can see now, bigger height can affect three aspects adversely at JVM level:
1) slower virtual/interface calls due to more casts/call site cache violations.
2) slower class/interface casts
3) bigger class metadata, bigger number of VMTs/IMTs.
Here in Scala collections we now do most of the calls via invokeinterface (as formal types almost everywhere are traits, not classes). These calls will not be affected, as count of superinterfaces and interface method tables remain the same at VM level.
Interestingly enough, with forwarder classes some of the invokeinterface calls can be translated into cheaper invokevirtual ones.
Class casts there also seems not to be a big problem.
Third issue however can be a problem for such VMs as Dalvik. Here we factor out many identical forwarder methods and pay for this by increased size of metadata and increaed number of VMTs.
Note however, that overall count of loaded classes will not increase - we already load T.class & T$class.class for each inherited interface, and initialize every T$class on object creation (as we call each T$class.$init$). The overall number of declared methods in all those classes will also not be increased substantially. Thus more VMTs (more precisely, same number of bigger VMTs) seems to be major potential problem for me.
Anyway, it's better to have all this issues to be profiled and checked in reality.
You are right, deep inheritance hierarchy can be a problem.That's the issue here: There's a much more complicated hierarchy than
just one or two traits. It's pretty extensive inside scala.collection,
and can result in some pretty deep inheritance trees for the final
concrete classes.So I'm not so sure that it's a clear win. It it could even be
detrimental (to actual runtime overhead) to create abstract class
layers for everything, including traits like TraversableLike which are
never meant to be inherited directly.
In this case hovewer, we already have deep inheritance hierarchy through interfaces at JVM level, and adding forwarder classes won't make class inheritance height deeper than current interface inheritance height.
As I can see now, bigger height can affect three aspects adversely at JVM level:
1) slower virtual/interface calls due to more casts/call site cache violations.
2) slower class/interface casts
3) bigger class metadata, bigger number of VMTs/IMTs.
Here in Scala collections we now do most of the calls via invokeinterface (as formal types almost everywhere are traits, not classes). These calls will not be affected, as count of superinterfaces and interface method tables remain the same at VM level.
Interestingly enough, with forwarder classes some of the invokeinterface calls can be translated into cheaper invokevirtual ones.
Class casts there also seems not to be a big problem.
Third issue however can be a problem for such VMs as Dalvik. Here we factor out many identical forwarder methods and pay for this by increased size of metadata and increaed number of VMTs.
Note however, that overall count of loaded classes will not increase - we already load T.class & T$class.class for each inherited interface, and initialize every T$class on object creation (as we call each T$class.$init$). The overall number of declared methods in all those classes will also not be increased substantially. Thus more VMTs (more precisely, same number of bigger VMTs) seems to be major potential problem for me.
Anyway, it's better to have all this issues to be profiled and checked in reality.
Sat, 2011-12-03, 08:27
#54
Re: Re: Size of standard library and possible tricks to reduce
суббота, 3 декабря 2011 г. 13:20:38 UTC+7 пользователь Pavel Pavlov написал:
3) bigger class metadata, bigger number of VMTs/IMTs.
...
Third issue however can be a problem for such VMs as Dalvik. Here we factor out many identical forwarder methods and pay for this by increased size of metadata and increaed number of VMTs.
Note however, that overall count of loaded classes will not increase - we already load T.class & T$class.class for each inherited interface, and initialize every T$class on object creation (as we call each T$class.$init$). The overall number of declared methods in all those classes will also not be increased substantially. Thus more VMTs (more precisely, same number of bigger VMTs) seems to be major potential problem for me.
Just remembered of so obvious optimization of abstract classes st JVM level: full elimination of IMT tables as they will never be used at runtime. Don't know if Dalvik does it or not.
Sat, 2011-12-03, 12:47
#55
Re: Re: Size of standard library and possible tricks to reduce
...
Its contents at bytecode level can be approximated here by contents of the "abstract class GenTraversableOnce$AC[+T] extends AnyRef with GenTraversableOnce[T]" plus current contents of the GenTraversableOnce$class.
...
If we declare its forwarders class as "abstract class Traversable$AC[+T] extends AnyRef with Traversable[T]" ...
But if we replace "AnyRef" here with first Traversable supertrait's forwarder class (TraversableLike$AC), ...
...
Loosing weight for Traversable requires creation of class TraversableLike$AC, which I just defined as "abstract class TraversableLike$AC[+T, +R] extends AnyRef with TraversableLike[T, R]".
Of course, all these transformations should be done by the compiler and will not require any assistance from the programmer.
All user's code will be automatically & transparently transformed, i.e. all the changes will be visible on the JVM level, on the Scala level nothing will change.
Mon, 2011-12-05, 15:27
#56
Re: Re: Size of standard library and possible tricks to reduce
A question on Stack Overflow led me to a new thought on this matter.
Assume the following got implemented:
1. A class is generated for every trait.
2. If something "extends" a trait, then the corresponding class is
used instead of forwarders.
Now, assume this _also_ gets implemented:
3. Add constructor parameters to traits.
In such a case, would there be any point in keeping "class" as a
language construct instead of an implementation detail?
On Thu, Dec 1, 2011 at 15:38, martin odersky wrote:
>
>
> On Thu, Dec 1, 2011 at 11:48 AM, Pavel Pavlov
> wrote:
>>
>> What if the compiler will create 'abstract class Foo$AC extends Foo' for
>> every trait Foo?
>> Then it will be able to rewrite every definition of the form 'class C
>> extends Foo ...' to 'class C extends Foo$AC ...', i.e. replace only the
>> first supertrait by generated superclass.
>> This will catch all the uses like 'new Iterator {...}' or 'C extends A =>
>> B' in both library and user's code.
>> Comparing to the now used scheme, extra code will be generated only for
>> those traits which are never used as first superclass.
>>
>> Moreover, it makes sense to combine Foo$class and Foo$AC into one class.
>> This will help to futher reduce bytecode size, as most of constant pool
>> entries will be unified in these classes.
>> So, Foo$class will contain two versions of every non-abstract Foo's
>> method: static method with original method's body (as now) and instance
>> method with stub that invokes that static.
>>
>> What do you think of this?
>>
>
> I don't know about doing it everywhere. Many traits are meant to be mixed
> into other traits before they are instantiated. Examples are all ...Like
> traits in the collection classes. Generating an abstract class for each of
> them would be pure waste, since no class ever inherits from them in first
> position.
>
> On the other hand, maybe an annotation could do the trick of giving more
> precise control to implementers without having to do a lot of typing.
> Something like
>
> @classbacked trait Iterator { ... }
>
> And in that case, I agree we should try to combine the abstract class with
> the implementation class. So both abstract class and implementation class
> could be called Iterator$class, which is neat - no new classfiles!
>
> There's one tricky issue: A static method (like the ones in the
> implementation class) may not collide with a dynamic method (like the ones
> in the abstract class), where collide means "have the same name and type
> signature". Collisions are possible, for instance in the following case:
>
> @classbacked trait T {
> def foo(x: T) = ???
> def foo() = ???
> }
>
> This will generate:
>
> class T$class {
> def foo(x: T) = T$class.foo(this, x)
> def foo() = T$class.foo(this)
>
> static def foo(_this: T, x: T) = ???
> static def foo(_this: T) = ???
> }
>
> Note the collision between the first instance foo and the last static foo.
>
> The compiler needs to check for collisions when generating T$class.
> Fortunately, there's a remedy: In case of collision, simply do not generate
> the instance member.
>
> Cheers
>
> -- Martin
>
>
>
>
>
> --
> Martin Odersky
> Prof., EPFL and Chairman, Typesafe
> PSED, 1015 Lausanne, Switzerland
> Tel. EPFL: +41 21 693 6863
> Tel. Typesafe: +41 21 691 4967
>
Mon, 2011-12-05, 15:57
#57
Re: Re: Size of standard library and possible tricks to reduce
Hi Daniel,
It's very interesting point.
However one issue remains unlear for me:
How will you solve the "diamond problem" with constructors?
C++ has so intricate semantics of virtual bases initialization right because of this.
There is an example:
================================
trait A(val x: Int, val y: Int)
trait B(b: Int) extends A(b, 1)
trait C(c: Int) extends A(c, 2)
trait D(b: Int, c: Int) extends B(b) with C(c)
val d = new D(3, 4)
println(d.x) // ???
println(d.y) // ???
================================
The diamond problem with instance methods is solved in Scala by linearization of supertraits, but the same problem with constructors still persists.
Regards,
Pavel.
понедельник, 5 декабря 2011 г. 21:23:03 UTC+7 пользователь Daniel Sobral написал:
It's very interesting point.
However one issue remains unlear for me:
How will you solve the "diamond problem" with constructors?
C++ has so intricate semantics of virtual bases initialization right because of this.
There is an example:
================================
trait A(val x: Int, val y: Int)
trait B(b: Int) extends A(b, 1)
trait C(c: Int) extends A(c, 2)
trait D(b: Int, c: Int) extends B(b) with C(c)
val d = new D(3, 4)
println(d.x) // ???
println(d.y) // ???
================================
The diamond problem with instance methods is solved in Scala by linearization of supertraits, but the same problem with constructors still persists.
Regards,
Pavel.
понедельник, 5 декабря 2011 г. 21:23:03 UTC+7 пользователь Daniel Sobral написал:
A question on Stack Overflow led me to a new thought on this matter.
Assume the following got implemented:1. A class is generated for every trait.
2. If something "extends" a trait, then the corresponding class is
used instead of forwarders.Now, assume this _also_ gets implemented:
3. Add constructor parameters to traits.
In such a case, would there be any point in keeping "class" as a
--
language construct instead of an implementation detail?Daniel C. Sobral
I travel to the future all the time.
Mon, 2011-12-05, 18:27
#58
Re: Re: Size of standard library and possible tricks to reduce
On Monday, December 5, 2011 9:23:03 AM UTC-5, Daniel Sobral wrote:
Not a good idea. Traits are different from classes for a reason: they avoid both the diamond problem and initialization order problem by not having initialization parameters.Now, assume this _also_ gets implemented:
3. Add constructor parameters to traits.
Mon, 2011-12-05, 20:27
#59
Re: Re: Size of standard library and possible tricks to reduce
On Mon, Dec 5, 2011 at 12:50, Pavel Pavlov wrote:
> Hi Daniel,
>
> It's very interesting point.
>
> However one issue remains unlear for me:
> How will you solve the "diamond problem" with constructors?
The same way it is already solved:
scala> trait A[X, Y]
defined trait A
scala> trait B[T] extends A[T, Int]
defined trait B
scala> trait C[T] extends A[T, Double]
defined trait C
scala> trait D[T1, T2] extends B[T1] with C[T2]
:10: error: illegal inheritance;
trait D inherits different type instances of trait A:
A[T2,Double] and A[T1,Int]
trait D[T1, T2] extends B[T1] with C[T2]
^
By making it illegal.
Note that this doesn't impose any additional restriction over what
classes already offer. Classes *already* make this kind of
double-inheritance illegal by making it impossible.
> C++ has so intricate semantics of virtual bases initialization right because
> of this.
>
> There is an example:
> ================================
> trait A(val x: Int, val y: Int)
> trait B(b: Int) extends A(b, 1)
> trait C(c: Int) extends A(c, 2)
>
> trait D(b: Int, c: Int) extends B(b) with C(c)
>
> val d = new D(3, 4)
> println(d.x) // ???
> println(d.y) // ???
> ================================
>
> The diamond problem with instance methods is solved in Scala by
> linearization of supertraits, but the same problem with constructors still
> persists.
>
> Regards,
> Pavel.
>
> понедельник, 5 декабря 2011 г. 21:23:03 UTC+7 пользователь Daniel Sobral
> написал:
>>
>> A question on Stack Overflow led me to a new thought on this matter.
>> Assume the following got implemented:
>>
>> 1. A class is generated for every trait.
>> 2. If something "extends" a trait, then the corresponding class is
>> used instead of forwarders.
>>
>> Now, assume this _also_ gets implemented:
>>
>> 3. Add constructor parameters to traits.
>>
>> In such a case, would there be any point in keeping "class" as a
>> language construct instead of an implementation detail?
>>
>> --
>>
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
Mon, 2011-12-05, 21:17
#60
Re: Re: Size of standard library and possible tricks to reduce
On Mon, Dec 5, 2011 at 2:23 PM, Daniel Sobral wrote:
>> However one issue remains unlear for me:
>> How will you solve the "diamond problem" with constructors?
>
> The same way it is already solved:
>
> scala> trait A[X, Y]
> defined trait A
>
> scala> trait B[T] extends A[T, Int]
> defined trait B
>
> scala> trait C[T] extends A[T, Double]
> defined trait C
>
> scala> trait D[T1, T2] extends B[T1] with C[T2]
> :10: error: illegal inheritance;
> trait D inherits different type instances of trait A:
> A[T2,Double] and A[T1,Int]
> trait D[T1, T2] extends B[T1] with C[T2]
> ^
However, say you have
trait A[T](foo: T)
trait B[T] extends A[T]
trait C[T] extends B[T] with A[T]
class D[T] extends C[T] with B[T]
Where's the correct place to initialize A.foo?
This is the reason C++ has virtual base classes, something that I feel
would really complicate Scala if added.
Mon, 2011-12-05, 22:17
#61
Re: Re: Size of standard library and possible tricks to reduce
Where's the correct place to initialize A.foo?
Guys,
I've just got to have a totally crazy idea about traits initialization.
What if we allow secondary (but not primary!) constructors in traits?
Then define a simple rule:
If a trait has any secondary constructors, exactly one of them must be called in any inheritance hierarchy containing this trait.
So, if we have
trait A {
val x: Int = _
def this(xx: Int) { x = xx }
}
trait T1 extends A
trait T2 extends A {
def this(xx: Int) { A.super(xx) }
def this(z: Double) {/*empty*/}
}
then these programs will be correct:
class C extends A(42)
class C0(x: Int) extends A(x)
class C1(x: Int) extends T1 with A(x)
class C2(x: Int) extends T2(x) // ok - A is initialized in T2
class C3(x: Int) extends T2(x) with A // ok - A is initialized in T2
class C4(x: Int) extends T2(3.14) with A(x) // ok - A is not initialized in T2
and these are ill-formed:
class B extends A // A is not initialized
class B1 extends T1 // A is not initialized
class B2(x: Int) extends T2(x) with A(x) // A is initialized twice
This way we can:
- define trait initialization requirements in Scala code (and check them in compiler);
- define initialization dependence of class/trait and its supertraits;
- shift the responsibility on trait initialization down the heirarchy to the point where all arguments can be provided.
Will this work or not? Has it any holes? It if works, can it replace pre-initialized fields?
Any thoughts?
Tue, 2011-12-06, 07:07
#62
Re: Re: Trait initialization (Size of standard library and poss
Am Montag, 5. Dezember 2011, 22:11:28 schrieb Pavel Pavlov:
> > Where's the correct place to initialize A.foo?
>
> Guys,
>
> I've just got to have a totally crazy idea about traits initialization.
>
> What if we allow secondary (but not primary!) constructors in traits?
>
> Then define a simple rule:
>
> If a trait has any secondary constructors, exactly one of them must be
> called in any inheritance hierarchy containing this trait.
>
> So, if we have
> trait A {
> val x: Int = _
> def this(xx: Int) { x = xx }
> }
> trait T1 extends A
> trait T2 extends A {
> def this(xx: Int) { A.super(xx) }
> def this(z: Double) {/*empty*/}
> }
>
> then these programs will be correct:
> class C extends A(42)
> class C0(x: Int) extends A(x)
> class C1(x: Int) extends T1 with A(x)
> class C2(x: Int) extends T2(x) // ok - A is initialized in T2
> class C3(x: Int) extends T2(x) with A // ok - A is initialized in T2
> class C4(x: Int) extends T2(3.14) with A(x) // ok - A is not
> initialized in T2
>
> and these are ill-formed:
> class B extends A // A is not initialized
> class B1 extends T1 // A is not initialized
> class B2(x: Int) extends T2(x) with A(x) // A is initialized twice
>
> This way we can:
> - define trait initialization requirements in Scala code (and check them
> in compiler);
> - define initialization dependence of class/trait and its supertraits;
> - shift the responsibility on trait initialization down the heirarchy to
> the point where all arguments can be provided.
>
> Will this work or not? Has it any holes? It if works, can it replace
> pre-initialized fields?
>
> Any thoughts?
It sounds very intriguing. Somehow I never liked the "early initialization"
syntax. The possibility of providing trait constructor parameters and
secondary constructors in the way you described is a lot more pleasant to my
eyes.
If it does not interact badly with other features this would be a very nice
addition. And as it mimics super class constructor calls it's in itself not a
new syntactic feature.
Nice idea!
Greetings
Bernd
Tue, 2011-12-06, 14:57
#63
Re: Re: Size of standard library and possible tricks to reduce
On Mon, Dec 5, 2011 at 18:07, Todd Vierling wrote:
> On Mon, Dec 5, 2011 at 2:23 PM, Daniel Sobral wrote:
>>> However one issue remains unlear for me:
>>> How will you solve the "diamond problem" with constructors?
>>
>> The same way it is already solved:
>>
>> scala> trait A[X, Y]
>> defined trait A
>>
>> scala> trait B[T] extends A[T, Int]
>> defined trait B
>>
>> scala> trait C[T] extends A[T, Double]
>> defined trait C
>>
>> scala> trait D[T1, T2] extends B[T1] with C[T2]
>> :10: error: illegal inheritance;
>> trait D inherits different type instances of trait A:
>> A[T2,Double] and A[T1,Int]
>> trait D[T1, T2] extends B[T1] with C[T2]
>> ^
>
> However, say you have
>
> trait A[T](foo: T)
> trait B[T] extends A[T]
> trait C[T] extends B[T] with A[T]
> class D[T] extends C[T] with B[T]
>
> Where's the correct place to initialize A.foo?
Well, since no one is passing a parameter to A, this is plainly incorrect.
If someone is passing parameters to A, then apply the same rules as
Scala applies for *type* parameters (with the appropriate changes) as
shown above.
Tue, 2011-12-06, 16:31
#64
Re: Re: Size of standard library and possible tricks to reduce
On Tue, Dec 6, 2011 at 8:49 AM, Daniel Sobral wrote:
>> However, say you have
>>
>> trait A[T](foo: T)
>> trait B[T] extends A[T]
>> trait C[T] extends B[T] with A[T]
>> class D[T] extends C[T] with B[T]
>>
>> Where's the correct place to initialize A.foo?
>
> Well, since no one is passing a parameter to A, this is plainly incorrect.
You don't get my point: There's two places where A[T] is inherited.
Which one should have the initialization parameter?
If you don't fully grok the problem introduced by having
initialization parameters for traits, read up on C++ virtual base
classes.
Tue, 2011-12-06, 16:41
#65
Re: Re: Size of standard library and possible tricks to reduce
On Tue, Dec 6, 2011 at 5:49 AM, Daniel Sobral wrote:
> On Mon, Dec 5, 2011 at 18:07, Todd Vierling wrote:
>> On Mon, Dec 5, 2011 at 2:23 PM, Daniel Sobral wrote:
>>>> However one issue remains unlear for me:
>>>> How will you solve the "diamond problem" with constructors?
>>>
>>> The same way it is already solved:
>>>
>>> scala> trait A[X, Y]
>>> defined trait A
>>>
>>> scala> trait B[T] extends A[T, Int]
>>> defined trait B
>>>
>>> scala> trait C[T] extends A[T, Double]
>>> defined trait C
>>>
>>> scala> trait D[T1, T2] extends B[T1] with C[T2]
>>> :10: error: illegal inheritance;
>>> trait D inherits different type instances of trait A:
>>> A[T2,Double] and A[T1,Int]
>>> trait D[T1, T2] extends B[T1] with C[T2]
>>> ^
>>
>> However, say you have
>>
>> trait A[T](foo: T)
>> trait B[T] extends A[T]
>> trait C[T] extends B[T] with A[T]
>> class D[T] extends C[T] with B[T]
>>
>> Where's the correct place to initialize A.foo?
>
> Well, since no one is passing a parameter to A, this is plainly incorrect.
>
> If someone is passing parameters to A, then apply the same rules as
> Scala applies for *type* parameters (with the appropriate changes) as
> shown above.
>
But that would mean the compiler needs to be able to decide equality
of value parameters. That looks tough to me :-)
I think the only possible alternative is to make value parameters to
traits optional and to check that only one instance of a trait is
parameterized. For instance, this would be OK:
trait A(a: T)
trait B(b: T) extends A // no parameters here
trait C(c: T) extends A(c) with B(c)
trait D extends B(d1) with C(d2)
And so would this:
trait A(a: T)
trait B(b: T) extends A(b)
trait C(c: T) extends A with B(c)
trait D extends B(d1) with C(d2)
But this would be illegal:
trait A(a: T)
trait B(b: T) extends A(b)
trait C(c: T) extends A(c) with B(c)
trait D extends B(d1) with C(d2)
Another possibility (which we explored earlier) would be to
translatetrait parameters to abstract vals and let linearization
decide which definition is current. That would have accepted the last
code with `a` in A initialized to d2. So the alternative is more
general, but it's also considerably harder to implement and I am not
sure it's what one wants in the end.
Cheers
Tue, 2011-12-06, 18:01
#66
Re: Re: Size of standard library and possible tricks to reduce
body p { margin-bottom: 0cm; margin-top: 0pt; }
martin odersky wrote:
I guess this means that 'class E[T](e: T) extends B(e)' is illegal, right? I think it may confuse people (esp. if you consider that you can't have a class extend 'trait F[T](f: T) extends B(f)' either)
Maybe require that traits like B are defined as 'abstract'? Then it would be more obvious why they can't be extended alone.
+1 for having a way for trait "constructor parameters". I need this all the time and defining an abstract 'val' for each, requiring a val definition in classes that extend is a lot of boilerplate.
Ittay
martin odersky wrote:
CAENVNkatXoXkHqKssg0mM5C_R7sYcpd26EtSMEJhdAujGzODiw [at] mail [dot] gmail [dot] com" type="cite">On Tue, Dec 6, 2011 at 5:49 AM, Daniel Sobralwrote: On Mon, Dec 5, 2011 at 18:07, Todd Vierlingwrote: On Mon, Dec 5, 2011 at 2:23 PM, Daniel Sobralwrote: However one issue remains unlear for me: How will you solve the "diamond problem" with constructors?The same way it is already solved: scala> trait A[X, Y] defined trait A scala> trait B[T] extends A[T, Int] defined trait B scala> trait C[T] extends A[T, Double] defined trait C scala> trait D[T1, T2] extends B[T1] with C[T2] <console>:10: error: illegal inheritance; trait D inherits different type instances of trait A: A[T2,Double] and A[T1,Int] trait D[T1, T2] extends B[T1] with C[T2] ^However, say you have trait A[T](foo: T) trait B[T] extends A[T] trait C[T] extends B[T] with A[T] class D[T] extends C[T] with B[T] Where's the correct place to initialize A.foo?Well, since no one is passing a parameter to A, this is plainly incorrect. If someone is passing parameters to A, then apply the same rules as Scala applies for *type* parameters (with the appropriate changes) as shown above.But that would mean the compiler needs to be able to decide equality of value parameters. That looks tough to me :-) I think the only possible alternative is to make value parameters to traits optional and to check that only one instance of a trait is parameterized. For instance, this would be OK: trait A(a: T) trait B(b: T) extends A // no parameters here trait C(c: T) extends A(c) with B(c) trait D extends B(d1) with C(d2)
I guess this means that 'class E[T](e: T) extends B(e)' is illegal, right? I think it may confuse people (esp. if you consider that you can't have a class extend 'trait F[T](f: T) extends B(f)' either)
Maybe require that traits like B are defined as 'abstract'? Then it would be more obvious why they can't be extended alone.
+1 for having a way for trait "constructor parameters". I need this all the time and defining an abstract 'val' for each, requiring a val definition in classes that extend is a lot of boilerplate.
Ittay
CAENVNkatXoXkHqKssg0mM5C_R7sYcpd26EtSMEJhdAujGzODiw [at] mail [dot] gmail [dot] com" type="cite">And so would this: trait A(a: T) trait B(b: T) extends A(b) trait C(c: T) extends A with B(c) trait D extends B(d1) with C(d2) But this would be illegal: trait A(a: T) trait B(b: T) extends A(b) trait C(c: T) extends A(c) with B(c) trait D extends B(d1) with C(d2) Another possibility (which we explored earlier) would be to translatetrait parameters to abstract vals and let linearization decide which definition is current. That would have accepted the last code with `a` in A initialized to d2. So the alternative is more general, but it's also considerably harder to implement and I am not sure it's what one wants in the end. Cheers
Tue, 2011-12-06, 18:31
#67
Re: Re: Size of standard library and possible tricks to reduce
What if we allow secondary (but not primary!) constructors in traits?
Of course, there is no difference between primary and secondary constructors. It is enough that trait should be inittialized exactly once for any instantiated subclass.
Tue, 2011-12-06, 19:01
#68
Re: Re: Size of standard library and possible tricks to reduce
On Tue, Dec 6, 2011 at 13:07, Todd Vierling wrote:
> On Tue, Dec 6, 2011 at 8:49 AM, Daniel Sobral wrote:
>>> However, say you have
>>>
>>> trait A[T](foo: T)
>>> trait B[T] extends A[T]
>>> trait C[T] extends B[T] with A[T]
>>> class D[T] extends C[T] with B[T]
>>>
>>> Where's the correct place to initialize A.foo?
>>
>> Well, since no one is passing a parameter to A, this is plainly incorrect.
>
> You don't get my point: There's two places where A[T] is inherited.
> Which one should have the initialization parameter?
>
> If you don't fully grok the problem introduced by having
> initialization parameters for traits, read up on C++ virtual base
> classes.
I grok, and I have answered, and you seem completely oblivious to my
point. So, I'll try a different tack.
A type parameter is a parameter.
It's a special kind of parameter, sure, but it still is a parameter.
So, replace "type parameter" by "parameter", and thing of "[T]" as
"(x)".
So the example I gave, and showed how Scala handles by running it on REPL, was:
trait A[X, Y]
trait B[T] extends A[T, Int]
trait C[T] extends A[T, Double]
trait D[T1, T2] extends B[T1] with C[T2]
Translated it would become:
trait A(x, y)
trait B(b) extends A(b, 1) // replacing Int with 1
trait C(c) extends A(c, 2) // replacing Double with 2
trait D(b, c) extends B(b) with C(c)
And the example I based it on, which was the "diamond problem example", was:
trait A(val x: Int, val y: Int)
trait B(b: Int) extends A(b, 1)
trait C(c: Int) extends A(c, 2)
trait D(b: Int, c: Int) extends B(b) with C(c)
See? Same thing. And it would be treated exactly how Scala already
treats the first example, aside from obvious differences between types
and values.
Tue, 2011-12-06, 19:11
#69
Re: Re: Size of standard library and possible tricks to reduce
вторник, 6 декабря 2011 г. 22:10:52 UTC+7 пользователь martin odersky написал:
On Tue, Dec 6, 2011 at 5:49 AM, Daniel Sobral <dcso...@gmail.com> wrote:What about secondary constructors for traits?
> On Mon, Dec 5, 2011 at 18:07, Todd Vierling <t...@duh.org> wrote:
>> On Mon, Dec 5, 2011 at 2:23 PM, Daniel Sobral <dcso...@gmail.com> wrote:
>>>> However one issue remains unlear for me:
>>>> How will you solve the "diamond problem" with constructors?
>>>
>>> The same way it is already solved:
>>>
>>> scala> trait A[X, Y]
>>> defined trait A
>>>
>>> scala> trait B[T] extends A[T, Int]
>>> defined trait B
>>>
>>> scala> trait C[T] extends A[T, Double]
>>> defined trait C
>>>
>>> scala> trait D[T1, T2] extends B[T1] with C[T2]
>>> <console>:10: error: illegal inheritance;
>>> trait D inherits different type instances of trait A:
>>> A[T2,Double] and A[T1,Int]
>>> trait D[T1, T2] extends B[T1] with C[T2]
>>> ^
>>
>> However, say you have
>>
>> trait A[T](foo: T)
>> trait B[T] extends A[T]
>> trait C[T] extends B[T] with A[T]
>> class D[T] extends C[T] with B[T]
>>
>> Where's the correct place to initialize A.foo?
>
> Well, since no one is passing a parameter to A, this is plainly incorrect.
>
> If someone is passing parameters to A, then apply the same rules as
> Scala applies for *type* parameters (with the appropriate changes) as
> shown above.
>
But that would mean the compiler needs to be able to decide equality
of value parameters. That looks tough to me :-)I think the only possible alternative is to make value parameters to
traits optional and to check that only one instance of a trait is
parameterized. For instance, this would be OK:trait A(a: T)
trait B(b: T) extends A // no parameters here
trait C(c: T) extends A(c) with B(c)
trait D extends B(d1) with C(d2)And so would this:
trait A(a: T)
trait B(b: T) extends A(b)
trait C(c: T) extends A with B(c)
trait D extends B(d1) with C(d2)But this would be illegal:
trait A(a: T)
trait B(b: T) extends A(b)
trait C(c: T) extends A(c) with B(c)
trait D extends B(d1) with C(d2)
What do you think - should we able to define a trait that can be initialized in two (or more) alternative ways?
Like this:
trait Alt(s: String) {
def this(x: Int, flag: Boolean) {
this(if (flag) x+"%" else "1/"+x)
}
}
val a = new Alt(123, true); val b = new Alt("?")
Should we have an ability to define conditionally initilatization-dependent traits?
Like in this example:
trait A(x: Int)
trait B(z: Double) extends A {
def this(x: Int) {
A.super(x)
}
}
val x1 = new B(1) // ok - A & B initialized
val x2 = new B(3.14) with A(42) // ok - A & B initialized
val x3 = new B(3.14) // error: A isn't initialized
val x4 = new B(1) with A(42) // error: A initialized twice
Tue, 2011-12-06, 19:51
#70
Re: Re: Size of standard library and possible tricks to reduce
Ah, now I see your point.
However, there are two difficulties there:
1) As Martin already said, to force compiler decide equality of values is overkill (if it's decidable at all)
2) How do you deal with side effects?
Consider an example:
trait A(val x: Int, val y: Int)
trait B(b: Int) extends A(b, 1)
trait C(c: Int) extends A(c, 2)
trait D(b: Int, c: Int, f: Int => Int, g: Int => Int) extends B(f(b)) with C(g(c))
def foo = 123
def bar(x: Int) = x
def baz(x: Int) = { launchMissiles(); x }
val y = new D(123, foo, bar, bar) // is this correct or not?
val x = new D(123, 123, baz, baz) // and this?
However, there are two difficulties there:
1) As Martin already said, to force compiler decide equality of values is overkill (if it's decidable at all)
2) How do you deal with side effects?
Consider an example:
trait A(val x: Int, val y: Int)
trait B(b: Int) extends A(b, 1)
trait C(c: Int) extends A(c, 2)
trait D(b: Int, c: Int, f: Int => Int, g: Int => Int) extends B(f(b)) with C(g(c))
def foo = 123
def bar(x: Int) = x
def baz(x: Int) = { launchMissiles(); x }
val y = new D(123, foo, bar, bar) // is this correct or not?
val x = new D(123, 123, baz, baz) // and this?
Tue, 2011-12-06, 20:11
#71
Re: Re: Size of standard library and possible tricks to reduce
Sorry, read this as:
.....
trait B(b: Int) extends A(b, 1)
trait C(c: Int) extends A(c, 1)
.....
.....
trait B(b: Int) extends A(b, 1)
trait C(c: Int) extends A(c, 1)
.....
Tue, 2011-12-06, 20:51
#72
Re: Re: Size of standard library and possible tricks to reduce
On Tue, Dec 6, 2011 at 16:26, Pavel Pavlov wrote:
> Ah, now I see your point.
>
> However, there are two difficulties there:
> 1) As Martin already said, to force compiler decide equality of values is
> overkill (if it's decidable at all)
Not necessarily. Let's take your example:
trait A(val x: Int, val y: Int)
trait B(b: Int) extends A(b, 1) // A.x = B.b, A.y = 1
trait C(c: Int) extends A(c, 2) // A.x = C.c, A.y = 2
trait D(b: Int, c: Int, f: Int => Int, g: Int => Int) extends B(f(b))
with C(g(c))
B.b = f(b)
C.c = g(c)
A.x = B.b = f(D.b)
A.x = C.c = g(D.c) // not direct parameter passing, so invalid
A.y = 1
A.y = 2 // different, so invalid, but, given your correction for it to
mean 1, this would be allowed
Note that even if C.c were equal to f(D.c) or f(D.b), it would _still_
be disallowed. However, this would be ok:
trait A(val x: Int, val y: Int)
trait B(b: Int) extends A(b, 1)
trait C(c: Int) extends A(c, 1) // A.x = C.c, A.y = 2
trait D(b: Int, c: Int, f: Int => Int, g: Int => Int) extends B(b) with C(b)
A.x = B.b = D.b
A.x = C.c = D.b
A.y = 1
A.y = 1
There's no need to evaluate anything here. For any trait, all
constructor parameters for parent traits will either be a literal,
equal to one of the trait's own parameters, or something else.
Literals can be compared, a trait's own parameters can be traced, and
everything else should simply be disallowed in case of conflict.
Note that this can deal with everything that is possible in Scala
right now, since Scala simply does not allow a class constructor
parameter to be initialized by more than one value.
> 2) How do you deal with side effects?
Side effects fall into the "something else" case. If there's any
conflict, where conflict is taken to mean more than one initialization
path, then it is disallowed.
>
> Consider an example:
>
>
> trait A(val x: Int, val y: Int)
> trait B(b: Int) extends A(b, 1)
> trait C(c: Int) extends A(c, 2)
> trait D(b: Int, c: Int, f: Int => Int, g: Int => Int) extends B(f(b)) with
> C(g(c))
This is declared invalid here, at declaration site.
>
> def foo = 123
> def bar(x: Int) = x
> def baz(x: Int) = { launchMissiles(); x }
>
> val y = new D(123, foo, bar, bar) // is this correct or not?
> val x = new D(123, 123, baz, baz) // and this?
It doesn't matter if it _could_ be correct at usage site or not. It is
allowed or disallowed at declaration.
I'll grant that the rules are more complex than the simple rules that
class offers. However, I think eliminating "class" altogether would
result in an overall _simplification_ of the language. You add the
initialization rules for values, and get rid of everything about
classes.
Tue, 2011-12-06, 21:11
#73
Re: Re: Size of standard library and possible tricks to reduce
An alternative to letting the compiler decide the equality of value
parameters is to check the equality at runtime. This would allow:
trait A(a: T)
trait B(b: T) extends A(b)
trait C(c: T) extends A(c) with B(c)
trait D extends B(d1) with C(d2)
throwing some sort of exception if d1 != d2. I think accords well with
the general intuition that there's only one A in a D, so that that A
can be initialized just one way. But it would be a pain to implement,
and you're still left with the question of whether it's really what
you want.
A
On Tue, Dec 6, 2011 at 7:10 AM, martin odersky wrote:
> On Tue, Dec 6, 2011 at 5:49 AM, Daniel Sobral wrote:
>> On Mon, Dec 5, 2011 at 18:07, Todd Vierling wrote:
>>> On Mon, Dec 5, 2011 at 2:23 PM, Daniel Sobral wrote:
>>>>> However one issue remains unlear for me:
>>>>> How will you solve the "diamond problem" with constructors?
>>>>
>>>> The same way it is already solved:
>>>>
>>>> scala> trait A[X, Y]
>>>> defined trait A
>>>>
>>>> scala> trait B[T] extends A[T, Int]
>>>> defined trait B
>>>>
>>>> scala> trait C[T] extends A[T, Double]
>>>> defined trait C
>>>>
>>>> scala> trait D[T1, T2] extends B[T1] with C[T2]
>>>> :10: error: illegal inheritance;
>>>> trait D inherits different type instances of trait A:
>>>> A[T2,Double] and A[T1,Int]
>>>> trait D[T1, T2] extends B[T1] with C[T2]
>>>> ^
>>>
>>> However, say you have
>>>
>>> trait A[T](foo: T)
>>> trait B[T] extends A[T]
>>> trait C[T] extends B[T] with A[T]
>>> class D[T] extends C[T] with B[T]
>>>
>>> Where's the correct place to initialize A.foo?
>>
>> Well, since no one is passing a parameter to A, this is plainly incorrect.
>>
>> If someone is passing parameters to A, then apply the same rules as
>> Scala applies for *type* parameters (with the appropriate changes) as
>> shown above.
>>
> But that would mean the compiler needs to be able to decide equality
> of value parameters. That looks tough to me :-)
>
> I think the only possible alternative is to make value parameters to
> traits optional and to check that only one instance of a trait is
> parameterized. For instance, this would be OK:
>
> trait A(a: T)
> trait B(b: T) extends A // no parameters here
> trait C(c: T) extends A(c) with B(c)
> trait D extends B(d1) with C(d2)
>
> And so would this:
>
> trait A(a: T)
> trait B(b: T) extends A(b)
> trait C(c: T) extends A with B(c)
> trait D extends B(d1) with C(d2)
>
> But this would be illegal:
>
> trait A(a: T)
> trait B(b: T) extends A(b)
> trait C(c: T) extends A(c) with B(c)
> trait D extends B(d1) with C(d2)
>
> Another possibility (which we explored earlier) would be to
> translatetrait parameters to abstract vals and let linearization
> decide which definition is current. That would have accepted the last
> code with `a` in A initialized to d2. So the alternative is more
> general, but it's also considerably harder to implement and I am not
> sure it's what one wants in the end.
>
> Cheers
>
> -- Martin
пятница, 2 декабря 2011 г. 21:49:34 UTC+7 пользователь Todd Vierling написал:
Ok, to be more specific on this, let us dive into all the tedious details. I will use Scala 2.9.1 here for getting experimental data.
Starting from the top of collections hierarchy, GenTraversableOnce contains 1 non-abstract method ("/:\") and thus its $class now contain 2 static methods ("/:\" and "$init$") and will contain 1 extra instance method with the proposed scheme (forwarder for "/:\").
Its contents at bytecode level can be approximated here by contents of the "abstract class GenTraversableOnce$AC[+T] extends AnyRef with GenTraversableOnce[T]" plus current contents of the GenTraversableOnce$class.
Now let's skip some traits and look at Traversable.
If we declare its forwarders class as "abstract class Traversable$AC[+T] extends AnyRef with Traversable[T]" then it will contain 111 forwarders (including those for all supertraits), whereas its $class now contains only 4 static impl. methods.
But if we replace "AnyRef" here with first Traversable supertrait's forwarder class (TraversableLike$AC), then Traversable$AC will have only 13 forwarders, of which 4 are forwarders for Traversable's own static impl. methods, and other 9 comes from all supertraits but first (GenTraversable, TraversableOnce, GenericTraversableTemplate).
The size of Traversable$AC.class is reduced then from 26647 to 4334 bytes.
Loosing weight for Traversable requires creation of class TraversableLike$AC, which I just defined as "abstract class TraversableLike$AC[+T, +R] extends AnyRef with TraversableLike[T, R]". This version of TraversableLike$AC contain now 98 forwarders, class size is 22632 bytes, so all fat from Traversable$AC is moved here.
Doing the same operation with TraversableLike (replacing AnyRef with first supertrait) won't give us much as first supertrait of TraversableLike is (unfortunately!) HasNewBuilder. The situation here can be made better only by manual reordering of TraversableLike supertraits.
But anyway, the code size of these two classes (22632 + 4334 bytes) is virtually the same as code size of _only one use_ of Traversable as first supertrait (like in "new Traversable {...}") in the current scheme (~26647 bytes)!
So I think this is clear win.
Now let's see what we have for other collection traits:
Iterable:
32383 bytes, 134 forwarders (added on every use) becomes 11336 bytes, 47 forwarders (added once)
Seq (again unlucky case, first supertrait is PartialFunction):
54186 bytes, ~280 forwarders (added on every use) => 44151 bytes, 200 forwarders (added once)
LinearSeq: 55220 b,~280 fwd => 4114 b, 20 fwd
IndexedSeq: 55283 b, 280 fwd => 4379 b, 21 fwd
imm.Traversable: 27344 b, 112 fwd => 2054 b, 6 fwd
imm.Iterable: 33314 b, 136 fwd => 12174 b, 50 fwd
imm.Seq: 55415 b,~280 fwd => 27589 b, 168 fwd
imm.LinearSeq: 56529 b, 284 fwd => 4431 b, 21 fwd
imm.IndexedSeq: 56599 b, 284 fwd => 4971 b, 23 fwd
muta.Traversable: 27250 b, 112 fwd => 2024 b, 6 fwd
muta.Iterable: 33196 b, 136 fwd => 12110 b, 50 fwd
muta.Seq: 56018 b,~285 fwd => 28283 b, 170 fwd
muta.LinearSeq: 57208 b,~290 fwd => 4283 b, 20 fwd
muta.IndexedSeq: 57972 b, 290 fwd => 5587 b, 27 fwd
muta.Buffer: 63377 b, 314 fwd => 10807 b, 47 fwd
Set: 47927 b,~243 fwd => 38691 b,~168 fwd (1st super: Function1)
imm.Set: 49007 b, 245 fwd => 21355 b, 133 fwd (1st super: imm.Iterable)
muta.Set: 55370 b,~290 fwd => 27534 b, 164 fwd (1st super: muta.Iterable)
imm.SortedSet: 52284 b, 261 fwd => 6702 b, 32 fwd
Map: 49041 b, 237 fwd => 20572 b, 123 fwd
imm.Map: 52760 b,~264 fwd => 24523 b, 139 fwd
muta.Map: 58590 b,~291 fwd => 29672 b, 165 fwd
Iterator: 21479 b, ~95 fwd => 11409 b, 52 fwd
PartialFunction: 11075 b, 78 fwd => 1892 b, 4 fwd
Function1: 10213 b, 75 fwd => 10213 b, 75 fwd
So, you can see that even in unlucky cases (when first supertrait does not provide major part of non-abstract methods, comparing to other supertraits), the overall number of forwarders as well as class file size is still decreased.
Now let's look at some real uses of traits in the library's code.
I've grep'ed collections/immutable and found 10 "good" subclasses of immutable.Set:
BitSet, HashSet, ListSet, EmptySet, Set1, Set2, Set3, Set4, MapProxy.keySet, SetProxy.newProxy (both through SetProxy).
Having forwarders class for imm.Set will lead to (10*49007-21355) = ~458K reduction of code size, (10*245-133) = 2317 lesser methods.
On the other hand, trait imm.SortedSet is never used as first supertrait in collections/immutable, so there we'll have extra unused 32 forwarders weighting 6702 bytes. Nevertheless, these 6K is worth to be generated, if there are some "good uses" in other parts of the library (having only 1 such use is enough to recoup all costs) or there are good chances such uses may occur in the code of library users.
So, as I wrote in my first message, code bloat for such unused-as-first-supertrait traits is the only (and unavoidable!) weak spot of proposed scheme, as far as I can see.
Anyway, I hope the amount of such unused code will remain much smaller than removed code duplication for most of real-world code bases.
I still cannot see how one can remove comparable amount of duplicated code without generate-forwarders-by-default approach.
Annotation-based scheme can help reduce code duplication in already known problem places (which must be found manually), but it will not prevent arising such problems in the future (or worse, at the library user's side).
Maybe, annotation with opposite default ("@NoForwarders trait A") will be enough there?