[rust-dev] std::num::pow() is inadequate / language concepts

[Gregor Cramer]

Hello Rust folk!

I am new to Rust, and I have doubts concerning current language concepts.

One example: in module ::std::num function pow() is defined:

pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T {
if exp == 1 { base }
else {
let mut acc = one::<T>();
while exp > 0 {
if (exp & 1) == 1 {
acc = acc * base;
}
base = base * base;
exp = exp >> 1;
}
acc
}
}

In general this implementation is ok, but not really usable with BigInt. Of
course, the call ':.std::num::pow(a, 1000)', 'a' is a BigInt, works. But this
implementation is not adequate for big integers. Firstly, too many memory
allocations during the computation (a specialized version can avoid these
memory allocations), secondly, for big integers a specialized function for
squaring (base * base) has to be used, because squaring can be done quite
more efficient than multiplication (with big integers). So this function is much
too slow and has to be overloaded, but:

1. Overloading is not supported (even the archaic C++ is providing this).

2. The footprint 'base: T' is not 100% suitable, for big integers the function
definition
fn pow(base: &BigInt, mut exp: uint) -> BigInt
would be more appropriate, because the argument 'base' needs not to be
modified (or reassigned), and a call by reference (avoiding a superfluous
memory allocation) is more efficient in this case.

Of cource, a specialized version of pow() could be implemented in trait
BigInt, but this is only a workaround. And if a user only knows
::std::num::pow(), he will use an inappropriate implementation without
being aware of this.

Probably in this case it might be a solution to move pow() into a trait, but
I'm speaking about a general problem. Rust 1.0 will be released, and someone
is developing a new module for version 1.1. But some of the functions in 1.0
are inadequate for the new module, how to solve this without changing the API
in 1.1? I think that function overloading may help in some cases, but the
problem with inappropriate footprints remains. In my opinion this
thing with the footprints (reference or not if the real type is unknown -
that's why the concept with 'const' in C++ exists) is a conceptual design
issue, but probably I do not yet fully understand Rust.

BTW: the functions next_power_of_two(), and checked_next_power_of_two()
are only defined for primitives (trait Primitive), but should also be
applicable for big integers, I think .

C heers,
Gregor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/43e6317c/attachment.html>

[Huon Wilson]

Probably in this case it might be a solution to move pow() into a
trait, but
I'm speaking about a general problem. Rust 1.0 will be released, and someone
is developing a new module for version 1.1. But some of the functions in 1.0
are inadequate for the new module, how to solve this without changing the API
in 1.1?

1.0 will not stabilise every function in every library; we have precise
stability attributes[1] so that the compiler can warn or error if you
are using functionality that is subject to change. The goal is to have
the entirety of the standard library classified and marked appropriately
for 1.0.


[1]: http://doc.rust-lang.org/master/rust.html#stability


Huon
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/337b9655/attachment.html>

[Tommy M. McGuire]

Post by Huon Wilson
1.0 will not stabilise every function in every library; we have precise
stability attributes[1] so that the compiler can warn or error if you
are using functionality that is subject to change. The goal is to have
the entirety of the standard library classified and marked appropriately
for 1.0.
[1]: http://doc.rust-lang.org/master/rust.html#stability

How would that solve the general problem? What would the stability of
pow() be if Gregor had not brought up the issue now?

[Huon Wilson]

Post by Tommy M. McGuire

Post by Huon Wilson
1.0 will not stabilise every function in every library; we have precise
stability attributes[1] so that the compiler can warn or error if you
are using functionality that is subject to change. The goal is to have
the entirety of the standard library classified and marked appropriately
for 1.0.
[1]: http://doc.rust-lang.org/master/rust.html#stability

How would that solve the general problem? What would the stability of
pow() be if Gregor had not brought up the issue now?

I was just pointing out that we aren't required to solve any/every
library issue before 1.0 (since the text I was quoting was rightfully
concerned about backwards incompatible API changes), not that this isn't
an issue.



Huon

[Patrick Walton]

Probably in this case it might be a solution to move pow() into a trait, but
I'm speaking about a general problem. Rust 1.0 will be released, and someone
is developing a new module for version 1.1. But some of the functions in 1.0
are inadequate for the new module, how to solve this without changing the API

If the signature is wrong and we mistakenly freeze it, we can just introduce a new function with a different name.

in 1.1? I think that function overloading may help in some cases, but the
problem with inappropriate footprints remains. In my opinion this
thing with the footprints (reference or not if the real type is unknown -
that's why the concept with 'const' in C++ exists) is a conceptual design
issue, but probably I do not yet fully understand Rust.

Overloading only helps some simple cases, and adds more complexity than it's worth (IMO).

The problem with C++ isn't that it doesn't have enough features. Rust is deliberately omitting some features from C++ that don't pull their weight. Overloading is one of them.

Patrick

[Gregor Cramer]

Hi Patrick,

Post by Patrick Walton
If the signature is wrong and we mistakenly freeze it, we can just introduce
a new function with a different name.

But this is a severe design issue, to introduce new function names. This makes
generic programming impossible. Now the user has to distinguish between
the types, but this is the task of the compiler.

Post by Patrick Walton
Overloading only helps some simple cases, and adds more complexity than it's worth (IMO).

Overloading is the only way to specialize functions, and this is the only way
to allow generic programming. Without specializing we are back to the bad
old days, where the user has to call the appropriate function for a specific
object, but in a modern programming language the compiler is doing these
things.

Post by Patrick Walton
The problem with C++ isn't that it doesn't have enough features. Rust is
deliberately omitting some features from C++ that don't pull their weight.
Overloading is one of them.

I think that some weights are unavoidable. And I cannot see serious drawbacks
with function overloading, but I see serious drawbacks without:

As I saw Rust the first time, I was impressed, and I decided to overwork the
big integer module (I've already written a big integer library in C), because
the current impementation is much too slow, it suffers from:

1. too many memory allocations
2. some algorithms are a bit naive.

And at first I tried to specialize std::num::pow(), but I gave up immediately,
because I cannot specialize. And without specializing this function I cannot
realize a proper implementation and design, and I'm never doing half-baken
things. So I gave up at all.

The current design in Rust does not allow:

1. Generic programming, in current design of Rust the user has to know,
which function to call for a specific object, and has to use switch (or match)
statements to call it (and if he forget the right functions and uses
std::num::pow(), his program will suffer). This is a programming style 30 years
ago, as I started to write programs.

2. Uniform function signatures, currently the user has to decide about using a
reference or not, but the compiler should decide. If the compiler is deciding,
whether an argument is given by value or by reference, then the problem with
the signature will vanish. And the compiler is better to decide than the user.
One more advantage: the user must not know whether to use a reference
or not when calling a function/method. One exception: a mutable argument, in
this case a reference will be used explicitely by the user, when specifiying
the signature, and when calling the function.

One more drawbacks without overloading: The user defines two print methods:

pub fn print(line : string) -> bool;
pub fn print(line : string, max_line_length : uint) -> bool;

Not possible, he has to use different names. An alternative definition would be:

pub fn print(line : string) -> bool;
pub fn print_with_maxlen(line : string, len : uint) -> bool;

30 years ago this was the normal way, but nowadays, it's a No-Go.

The current status of Rust is: it does not allow proper software design. And
that's bad, because a successor for C++ is needed. Of course, a successor
of C++ does not mean: a better C++. It means, a completely new language
conecept, like Rust. And it does not mean: avoid the good things of C++,
like specialization of functions.

Cheers,
Gregor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/dbf13083/attachment.html>

[Marijn Haverbeke]

Hello Gregor,

Firstly, blanket statements like "This makes generic programming
impossible" and "it does not allow proper software design" are
unneccesary hyperbole, and do not help the discussion in any way.

Traits provide a more well-defined, easier to reason about alternative
to overloading. They do require the author of an algorithm to decide
ahead of time whether this algorithm needs to be specializeable, which
I guess C++-style overloading does not. Whether that is a good or a
bad thing is debatable, but it is not true that Rust lacks a feature
for specialization.

Best,
Marijn

[Gregor Cramer]

Hi Marijn,

Post by Marijn Haverbeke
Firstly, blanket statements like "This makes generic programming
impossible" and "it does not allow proper software design" are
unneccesary hyperbole, and do not help the discussion in any way.

You're not right, my statement wasn't blanket, it was my result
after I tried to overwork the big integer library, and I have mentioned this:
I gave up at all. (I'm doing software design and implementation since
more than 30 years, and I never accept compromises, this is the way
how to develop magnificient software).

Post by Marijn Haverbeke
Traits provide a more well-defined, easier to reason about alternative
to overloading. They do require the author of an algorithm to decide
ahead of time whether this algorithm needs to be specializeable, which
I guess C++-style overloading does not.

Yes, the traits are great, I'm impressed, as I said before, and in fact Rust
is really great, despite a few facts, otherwise I wouldn't subscribe to
this mailing list. And my goal is to be constructive, don't worry if I'm
a bit euphoric, such things happens. Nethertheless, it gave up to overwork
the big integer libary because I cannot specialize std::num::pow(). There is
no way to proceed with a proper design.

Post by Marijn Haverbeke
Whether that is a good or a
bad thing is debatable, but it is not true that Rust lacks a feature
for specialization.

There is a lack in the current language concept, std::num::pow()
is inadequate due to this language concept, and std::num::pow() is
only one example for this fact.

I will repeat the problem with signatures. Currently pow() is declared
as following:

pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T;

That't 100% ok. The user will call this function in this way:

pow(a) // a is i32

Perfect. Now I need a specialized function for BigInt:

[#overload]
pub fn pow(base: &BigInt, mut exp: uint) -> T;

There's a problem (beside the missing overloading feature): the
specialized version requires a reference. Same problem if I'm
calling this function:

pow(&a) // a is BigInt

The user has to know how to call a function, depending on the type.
But a proper function specialization would be:

[#overload]
pub fn pow(base: BigInt, mut exp: uint) -> T;

And so the function call is as expected, like with other numeric types:

pow(a) // a is BigInt

But there is now a problem in this function definition, BigInt is given as
a copy, and this is a software design issue (superfluous memory allocation).
And this currently happens if the user is calling std::num::pow() with a
numeric type like BigInt (apart from other performance penalties in pow()).

That's what I've mentioned that the compiler should decide whether an
argument is given by reference or by value. In this way the latter approach
works. And in the case that a function willl modify an argument (in-out
value), for example:

fn mul_vec(acc : &mut [BigDigit], base: &mut [BigDigit], mut exp:uint)

the call of this function would be:

mul_vec(&a, &b, exp)

This concept will not change, because here it has to be clear that an argument
will be changed (furthermore the compiler should give a warning if a function
is not changing a mutable argument). I think that this approach is even
superior to the 'const' concept of C++, and it fit's with the great overall
concept of Rust (especially with the owner/borrower concept).

I try to show the problems if function specialization (overloading) is not
supported. A stable software design is problematic. Adding a new module,
which will use existing function declarations, is impossible in some cases.
Currently I cannot implement a specialized version of pow() for BigInt, adding
a new function for a different numeric type is only a hack, and moving this
function into a trait is not solving the general problem, because pow() is
only one example. (Beside: it's not my decision to move pow() into a trait.)

Cheers,
Gregor

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/6046a6f5/attachment.html>

[Jason Fager]

For the specific issue of exponentiation, you might be interested in
https://github.com/rust-lang/rfcs/pull/172

Post by Gregor Cramer
Hi Marijn,

Post by Marijn Haverbeke
Firstly, blanket statements like "This makes generic programming
impossible" and "it does not allow proper software design" are
unneccesary hyperbole, and do not help the discussion in any way.

You're not right, my statement wasn't blanket, it was my result
I gave up at all. (I'm doing software design and implementation since
more than 30 years, and I never accept compromises, this is the way
how to develop magnificient software).

Post by Marijn Haverbeke
Traits provide a more well-defined, easier to reason about alternative
to overloading. They do require the author of an algorithm to decide
ahead of time whether this algorithm needs to be specializeable, which
I guess C++-style overloading does not.

Yes, the traits are great, I'm impressed, as I said before, and in fact Rust
is really great, despite a few facts, otherwise I wouldn't subscribe to
this mailing list. And my goal is to be constructive, don't worry if I'm
a bit euphoric, such things happens. Nethertheless, it gave up to overwork
the big integer libary because I cannot specialize std::num::pow(). There is
no way to proceed with a proper design.

Post by Marijn Haverbeke
Whether that is a good or a
bad thing is debatable, but it is not true that Rust lacks a feature
for specialization.

There is a lack in the current language concept, std::num::pow()
is inadequate due to this language concept, and std::num::pow() is
only one example for this fact.
I will repeat the problem with signatures. Currently pow() is declared
pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T;
pow(a) // a is i32
[#overload]
pub fn pow(base: &BigInt, mut exp: uint) -> T;
There's a problem (beside the missing overloading feature): the
specialized version requires a reference. Same problem if I'm
pow(&a) // a is BigInt
The user has to know how to call a function, depending on the type.
[#overload]
pub fn pow(base: BigInt, mut exp: uint) -> T;
pow(a) // a is BigInt
But there is now a problem in this function definition, BigInt is given as
a copy, and this is a software design issue (superfluous memory allocation).
And this currently happens if the user is calling std::num::pow() with a
numeric type like BigInt (apart from other performance penalties in pow()).
That's what I've mentioned that the compiler should decide whether an
argument is given by reference or by value. In this way the latter approach
works. And in the case that a function willl modify an argument (in-out
fn mul_vec(acc : &mut [BigDigit], base: &mut [BigDigit], mut exp:uint)
mul_vec(&a, &b, exp)
This concept will not change, because here it has to be clear that an argument
will be changed (furthermore the compiler should give a warning if a function
is not changing a mutable argument). I think that this approach is even
superior to the 'const' concept of C++, and it fit's with the great overall
concept of Rust (especially with the owner/borrower concept).
I try to show the problems if function specialization (overloading) is not
supported. A stable software design is problematic. Adding a new module,
which will use existing function declarations, is impossible in some cases.
Currently I cannot implement a specialized version of pow() for BigInt, adding
a new function for a different numeric type is only a hack, and moving this
function into a trait is not solving the general problem, because pow() is
only one example. (Beside: it's not my decision to move pow() into a trait.)
Cheers,
Gregor
_______________________________________________
Rust-dev mailing list
Rust-dev at mozilla.org
https://mail.mozilla.org/listinfo/rust-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/e8f8f8c4/attachment.html>

[Christoph Husse]

Post by Gregor Cramer
I gave up at all. (I'm doing software design and implementation since
more than 30 years, and I never accept compromises, this is the way
how to develop magnificient software).

Hum, I would almost strongly disagree. I would even go as far as
saying that you won't develop any kind of reasonable software outside
of academic environments without making a whole fairytale of
compromises. In fact, everything is a compromise. Besides that, giving
up just because you can't overload functions, in a language that is
still evolving also sounds rather strange. More legit would be to
mention the issue, ask how the designers of the language would solve
it and maybe suggest what could be improved etc...

Post by Gregor Cramer
the big integer libary because I cannot specialize std::num::pow(). There is
no way to proceed with a proper design.

Well, I guess you did nothing but C++ in the last 30 years then?
Because I can't recall many languages that would allow this sort of
thing. How would C# and Java's Math::Pow() would work out in this
case? How would it work out in C? How would it work out in Python,
JavaScript, etc... the list is ... quite long.

The question is always about compromise. Shall rust include a language
feature to make some things easier for the sake of introducing tons of
problems as well?
Java is about the least expressive language we have at the time
(appears a bit like the greatest common denominator of all imperative
languages) and I would say only few people are out there who would say
that you can't do proper software design with it. It might not be a
concise and pleasing as "GOOD C++ design is", but then again "GOOD C++
design" is very hard to archieve and thus begs the questions if it is
even worth it to make a language that complicated so that magnificient
(academic) design is possible at the cost of making the average
(industrial) design horrible.

Post by Gregor Cramer
pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T;

I agree this definition appears to be very strange to me. In more than
one way. First it implies that the existing implementation works by
somehow multiplying types with the expontential trick " a * a = b, b *
b = c, c * c = a^6" etc...
This is an unacceptable restriction for me, as this kind of evaluation
might not be the best in many cases and we are talking about a
standard library function after all. It should always allow the BEST
implementation, not just some implementation.

Here we clearly need a better concept. And this concept needs to be
designed & defined. And you could start by doing this, instead of just
giving up ;).

[Christoph Husse]

Sorry... I meant a^8 xD...

And overlaoding is not a great concept in general, IMO.
What Rust could do is copy template specialization. So that I can say:

pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T; //
uses the exponential trick

pub fn pow<i64>(mut base: i64, mut exp: uint) -> i64; // uses some
cool processor features if available

pub fn pow<BigInt>(mut base: &BigInt, mut exp: uint) -> BigInt; //
uses some mighty algorithm that is not naive ;)

This avoids the horrible confusing of having functions acting totally
different depending on parameter count. Of course there should still
be the requirement in place that all specializations fulfill the
original template contraints. And in the best case also need to
fullfill some generic unitests that give a specification to ensure
that the user is not confused by this sort of "overloading".


On Fri, Jul 25, 2014 at 6:47 PM, Christoph Husse

Post by Christoph Husse

Post by Gregor Cramer
I gave up at all. (I'm doing software design and implementation since
more than 30 years, and I never accept compromises, this is the way
how to develop magnificient software).

Hum, I would almost strongly disagree. I would even go as far as
saying that you won't develop any kind of reasonable software outside
of academic environments without making a whole fairytale of
compromises. In fact, everything is a compromise. Besides that, giving
up just because you can't overload functions, in a language that is
still evolving also sounds rather strange. More legit would be to
mention the issue, ask how the designers of the language would solve
it and maybe suggest what could be improved etc...

Post by Gregor Cramer
the big integer libary because I cannot specialize std::num::pow(). There is
no way to proceed with a proper design.

Well, I guess you did nothing but C++ in the last 30 years then?
Because I can't recall many languages that would allow this sort of
thing. How would C# and Java's Math::Pow() would work out in this
case? How would it work out in C? How would it work out in Python,
JavaScript, etc... the list is ... quite long.
The question is always about compromise. Shall rust include a language
feature to make some things easier for the sake of introducing tons of
problems as well?
Java is about the least expressive language we have at the time
(appears a bit like the greatest common denominator of all imperative
languages) and I would say only few people are out there who would say
that you can't do proper software design with it. It might not be a
concise and pleasing as "GOOD C++ design is", but then again "GOOD C++
design" is very hard to archieve and thus begs the questions if it is
even worth it to make a language that complicated so that magnificient
(academic) design is possible at the cost of making the average
(industrial) design horrible.

Post by Gregor Cramer
pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T;

I agree this definition appears to be very strange to me. In more than
one way. First it implies that the existing implementation works by
somehow multiplying types with the expontential trick " a * a = b, b *
b = c, c * c = a^6" etc...
This is an unacceptable restriction for me, as this kind of evaluation
might not be the best in many cases and we are talking about a
standard library function after all. It should always allow the BEST
implementation, not just some implementation.
Here we clearly need a better concept. And this concept needs to be
designed & defined. And you could start by doing this, instead of just
giving up ;).

[Oscar Boykin]

Did I miss a point in this thread where using a typeclass/trait to
implement exponentiation was dismissed?

This function could be changed to:

fn pow<T: HasPow>(base: T, exp: uint) -> T { base.pow(exp) }

trait HasPow {
fn pow(self: Self, exp: uint) -> Self
}

Or, just use HasPow in your code.

Why is this not a solution?


On Fri, Jul 25, 2014 at 6:53 AM, Christoph Husse <

Post by Christoph Husse
Sorry... I meant a^8 xD...
And overlaoding is not a great concept in general, IMO.
pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T; //
uses the exponential trick
pub fn pow<i64>(mut base: i64, mut exp: uint) -> i64; // uses some
cool processor features if available
pub fn pow<BigInt>(mut base: &BigInt, mut exp: uint) -> BigInt; //
uses some mighty algorithm that is not naive ;)
This avoids the horrible confusing of having functions acting totally
different depending on parameter count. Of course there should still
be the requirement in place that all specializations fulfill the
original template contraints. And in the best case also need to
fullfill some generic unitests that give a specification to ensure
that the user is not confused by this sort of "overloading".
On Fri, Jul 25, 2014 at 6:47 PM, Christoph Husse

Post by Christoph Husse

Post by Gregor Cramer
I gave up at all. (I'm doing software design and implementation since
more than 30 years, and I never accept compromises, this is the way
how to develop magnificient software).

Hum, I would almost strongly disagree. I would even go as far as
saying that you won't develop any kind of reasonable software outside
of academic environments without making a whole fairytale of
compromises. In fact, everything is a compromise. Besides that, giving
up just because you can't overload functions, in a language that is
still evolving also sounds rather strange. More legit would be to
mention the issue, ask how the designers of the language would solve
it and maybe suggest what could be improved etc...

Post by Gregor Cramer
the big integer libary because I cannot specialize std::num::pow().

There is

Post by Christoph Husse

Post by Gregor Cramer
no way to proceed with a proper design.

Well, I guess you did nothing but C++ in the last 30 years then?
Because I can't recall many languages that would allow this sort of
thing. How would C# and Java's Math::Pow() would work out in this
case? How would it work out in C? How would it work out in Python,
JavaScript, etc... the list is ... quite long.
The question is always about compromise. Shall rust include a language
feature to make some things easier for the sake of introducing tons of
problems as well?
Java is about the least expressive language we have at the time
(appears a bit like the greatest common denominator of all imperative
languages) and I would say only few people are out there who would say
that you can't do proper software design with it. It might not be a
concise and pleasing as "GOOD C++ design is", but then again "GOOD C++
design" is very hard to archieve and thus begs the questions if it is
even worth it to make a language that complicated so that magnificient
(academic) design is possible at the cost of making the average
(industrial) design horrible.

Post by Gregor Cramer
pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T;

I agree this definition appears to be very strange to me. In more than
one way. First it implies that the existing implementation works by
somehow multiplying types with the expontential trick " a * a = b, b *
b = c, c * c = a^6" etc...
This is an unacceptable restriction for me, as this kind of evaluation
might not be the best in many cases and we are talking about a
standard library function after all. It should always allow the BEST
implementation, not just some implementation.
Here we clearly need a better concept. And this concept needs to be
designed & defined. And you could start by doing this, instead of just
giving up ;).

_______________________________________________
Rust-dev mailing list
Rust-dev at mozilla.org
https://mail.mozilla.org/listinfo/rust-dev

[Patrick Walton]

Post by Oscar Boykin
Did I miss a point in this thread where using a typeclass/trait to
implement exponentiation was dismissed?
fn pow<T: HasPow>(base: T, exp: uint) -> T { base.pow(exp) }
trait HasPow {
fn pow(self: Self, exp: uint) -> Self
}
Or, just use HasPow in your code.
Why is this not a solution?

Yes, I was about to bring this up. You might want to conceivably have
different types for the parameters, which Associated Types would solve
nicely. For the maximum genericity:

trait Pow {
type This;
type Exp;
type Result;
fn pow(this: This, exp: Exp) -> Result;
}

You can then write functions that take Powable things:

fn whatever<P:Pow>(p: P) -> P {
p.pow(p, 1)
}

Now the only restriction that is left is that all instances of `Pow`
must have the same number of arguments. Presumably this is not too
onerous. :)

Patrick

[Gregor Cramer]

Post by Oscar Boykin
Did I miss a point in this thread where using a typeclass/trait to
implement exponentiation was dismissed?
fn pow<T: HasPow>(base: T, exp: uint) -> T { base.pow(exp) }
trait HasPow {
fn pow(self: Self, exp: uint) -> Self
}
Or, just use HasPow in your code.

Yes, you missed a point, I've already pointed out in my initial mail that
moving pow() into a trait (that's what your code is finally doing) is solving
this special problem, but it is not solving a general problem with (other)
functions. A new module may cause that an older function (which you
cannot overload) is inadequate. This makes software instable. In the past
(with some older programming languages) you did not have solutions for
this, but Rust is 2014, programming and compiler techniques have evolved.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/debf214e/attachment.html>

[Gregor Cramer]

Post by Gregor Cramer
I gave up at all. (I'm doing software design and implementation since
more than 30 years, and I never accept compromises, this is the way
how to develop magnificient software).

Hum, I would almost strongly disagree I would even go as far as
saying that you won't develop any kind ...

How can you disagree about what I'm doing?

Well, I guess you did nothing but C++ in the last 30 years then?
Because I can't recall many languages that would allow this sort of
thing. How would C# and Java's Math::Pow() would work out in this
case? How would it work out in C? How would it work out in Python,
JavaScript, etc... the list is ... quite long.

I don't care about the capabilities of other languages, I don't use a
language if it is not appropriate.

The question is always about compromise. Shall rust include a language
feature to make some things easier for the sake of introducing tons of
problems as well?

No. Everyone is talking about tons of problems, but which ones?
The most problematic language, with tons of problems, is C++.
But even in C++ not overloading is the problem - and I have about
20 years experience with C++ - it is for example, to name just one,
the implicit casting, because this makes overloading a bit problematic.

Java is about the least expressive language we have at the time
(appears a bit like the greatest common denominator of all imperative
languages) and I would say only few people are out there who would say
that you can't do proper software design with it.

This depends on how your are doing software design. Impossible
for me to use Java.

It might not be a
concise and pleasing as "GOOD C++ design is", but then again "GOOD C++
design" is very hard to archieve and thus begs the questions if it is
even worth it to make a language that complicated so that magnificient
(academic) design is possible at the cost of making the average
(industrial) design horrible.

I cannot see that overloading is horrible or complicated. It's another
point that C++ is horrible and complicated. We have 2014, as I started
with C++ it was the superior language, but software design has evolved,
nowadays object oriented design is obscure, and that's in fact
my own experience. But C++ already supported one ingenious feature:
generic programming (but very low level).

Post by Gregor Cramer
pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T;

I agree this definition appears to be very strange to me. In more than
one way. First it implies that the existing implementation works by
somehow multiplying types with the expontential trick " a * a = b, b *
b = c, c * c = a^6" etc...
This is an unacceptable restriction for me, as this kind of evaluation
might not be the best in many cases and we are talking about a
standard library function after all. It should always allow the BEST
implementation, not just some implementation.
Here we clearly need a better concept. And this concept needs to be
designed & defined. And you could start by doing this, instead of just
giving up ;).

This means that I have to design at a lower level, before I start to implement
the big number library. Probably I'll try it, I don't know yet. I don't know
yet whether I will really use Rust. (BTW: "I gave up at all" does not mean
forever, please be aware that I'm not a native English speaker.)
In fact I'm looking for an alternative to C++, and Rust is still the most
promising one, but Rust is not yet elaborated (I know that Rust is still
pre-alpha).

And overlaoding is not a great concept in general, IMO.
pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T; //
uses the exponential trick
pub fn pow<i64>(mut base: i64, mut exp: uint) -> i64; // uses some
cool processor features if available
pub fn pow<BigInt>(mut base: &BigInt, mut exp: uint) -> BigInt; //
uses some mighty algorithm that is not naive

Yes, that would possibly be one solution for overloading, Unfortunately
the problem with the signature remains. It's absolutely clear for me
that an overloading feature should not cause problems, this means
that a design is required which suits perfectly with the principle design
of Rust.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/95e472a4/attachment.html>

[comex]

Post by Gregor Cramer
I don't care about the capabilities of other languages, I don't use a
language if it is not appropriate.

Appropriate for what? You seem to be claiming that stable code in
general needs this feature, so that's consigning all of the languages
listed to be inappropriate for virtually anything. But they're not,
so their design decisions should be considered, although of course
they're not necessarily right.

Post by Gregor Cramer
No. Everyone is talking about tons of problems, but which ones?
The most problematic language, with tons of problems, is C++.
But even in C++ not overloading is the problem - and I have about
20 years experience with C++ - it is for example, to name just one,
the implicit casting, because this makes overloading a bit problematic.

A few months ago I posted in a similar thread why I don't like overloading:

https://mail.mozilla.org/pipermail/rust-dev/2014-May/009982.html

Buy it or not, I don't think overloading is necessary, since most of
the time operations with room for such efficiency improvements should
be implemented either in traits or as ad-hoc methods. That is, I'd
call this a bug in std::num::pow.

And of course it's possible to change something to a trait after the
fact without breaking API compatibility.

[Gregor Cramer]

Post by comex
And of course it's possible to change something to a trait after the
fact without breaking API compatibility.

How you are doing this? I'm in fact a newbie in Rust, and it's interesting
that this can be done. std::num::pow() is a good example, I think.
Suppose I already have a program which is using std::num::pow() with a
self defined integer type. Now you are changing std::num::pow(), moving
the functionality into a trait. And my program will still compile and work
as before?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/cd1b0743/attachment.html>

[Sean McArthur]

Post by Gregor Cramer
How you are doing this? I'm in fact a newbie in Rust, and it's interesting
that this can be done. std::num::pow() is a good example, I think.
Suppose I already have a program which is using std::num::pow() with a
self defined integer type. Now you are changing std::num::pow(), moving
the functionality into a trait. And my program will still compile and work
as before?

I'd expect that std::num::pow() would gain a #[deprecated = "Use Pow
trait"] attribute, and be removed after Rust's deprecation period (which
pre-1.0 is pretty much a few commits later).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/1eb368ae/attachment.html>

[Christoph Husse]

Post by Gregor Cramer
How can you disagree about what I'm doing?

I don't. I disagree with that: " I never accept compromises, this is
the way how to develop magnificient software"
Because it's not. Unless you use magnificient only in academic context.

Post by Gregor Cramer
I don't care about the capabilities of other languages, I don't use a language if it is not appropriate.

C++ is not appropiate for almost any task there is. I am using C++
quite a lot, because at my work, C++ is the right tool for the job.
But there aren't many jobs for which this is true.

Post by Gregor Cramer
No. Everyone is talking about tons of problems, but which ones?

I am sure some language designers can give you more insight. I lack
the convincing arguments.

Post by Gregor Cramer
But even in C++ not overloading is the problem - and I have about

It's not so much about wether or not overloading could be used in rust
without causing really painful issues. The question is if overlaoding
fits into the language's design principles. Overloading is not
necessary. It's just one of many ways that lead to Rome.

Post by Gregor Cramer
This depends on how your are doing software design. Impossible for me to use Java.

Some of the greatest minds in the industry use Java for excellent
software design.
People read code, most of the time. People need to work with code
other people wrote most of the time. Agile projects need good tooling,
speaking of refactoring, code coverage, code formatting, coding
standards, build tools, packaging, dependency managment in particular.
C++ gives you almost nothing in any of those. C++ is a huge pain in
the ass in most regards. Unless you really need it to get the job
done, it's the worst choice there is.
A language is about more than just "what you consider beautiful,
etc."... It's about wether it allows agile, fast paced development
across diverse teams and average programmers can produce code anyone
else can read without getting eye cancer. That does not apply to C++
at all.

Post by Gregor Cramer
I cannot see that overloading is horrible or complicated. It's another

No, but it might be unnecessary.

[Gregor Cramer]

Post by Christoph Husse
I disagree with that: " I never accept compromises, this is
the way how to develop magnificient software"
Because it's not. Unless you use magnificient only in academic context.

????? I'm not doing academic things.

Post by Christoph Husse
It's not so much about wether or not overloading could be used in rust
without causing really painful issues. The question is if overlaoding
fits into the language's design principles.

I agree, if overloading does not fit at all, then it should not be done.

Post by Christoph Husse
Overloading is not necessary. It's just one of many ways that lead to Rome.

Yes, many ways are leading to Rome. One of the ways is easy to go,
and is a joy. Another way is tedious or cumbersome.

Post by Christoph Husse
A language is about more than just "what you consider beautiful,
etc."... It's about wether it allows agile, fast paced development
across diverse teams and average programmers can produce code anyone
else can read without getting eye cancer.

Fast-paced development without generic programming? And overloading
is supporting generic programming.

Post by Christoph Husse

Post by Gregor Cramer
I cannot see that overloading is horrible or complicated. It's another

No, but it might be unnecessary.

Possibly I'm wrong that overloading is neccessary in Rust, that's why
I'm talking, I'm not a master in Rust programming. But fact is: as I
stumbled over std::num::pow() I could see problems if not
having overloading. And I repeat: std::num::pow() is only an
example for a general problem.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/4208d5e1/attachment.html>

[Patrick Walton]

Post by Gregor Cramer
pow(a) // a is BigInt
But there is now a problem in this function definition, BigInt is given as
a copy, and this is a software design issue (superfluous memory allocation).
And this currently happens if the user is calling std::num::pow() with a
numeric type like BigInt (apart from other performance penalties in pow()).

That solution doesn't work for generic code, because Rust doesn't do
ad-hoc templates like C++. A function that is generic over the bigint
and int "pow" functions has to have one signature for "pow". Otherwise
you could get errors during template instantiation time, which is
something Rust strictly avoids.

Post by Gregor Cramer
That's what I've mentioned that the compiler should decide whether an
argument is given by reference or by value.

That doesn't work. It would have numerous problems with the borrow
check, etc.

Post by Gregor Cramer
I try to show the problems if function specialization (overloading) is not
supported.

Sorry, but it's not convincing to me.

Patrick

[范长春]

Hi all,


I have an idea about data types here.
We have two `product types` here, tuples and structs, but only one `sum types`, which is `enum`.
The tuple's members have anonymous names. There is a missing type which is `sum type`with anonymous members.


Why shouldn't we have another simpler `sum type` here. It can be defined like `type sum_type = int | &str | (int, &str)`.
It is like `enum`, but the members are anonymous.


Now, the function overloading is very obvious. `fn overload( arg : sum_type ) ` is just fine.


And, IMHO, this design is much clearer than traditional overloading, more explicit.


Apologize for my poor English. Feel free to ignore my proposal if it's silly.


Thanks,
Changchun


------------------ Original ------------------
From: "Gregor Cramer";<remarcg at gmx.net>;
Date: Fri, Jul 25, 2014 06:47 PM
To: "rust-dev"<rust-dev at mozilla.org>;

Subject: Re: [rust-dev] std::num::pow() is inadequate / language concepts




Hi Patrick,

Post by Patrick Walton
If the signature is wrong and we mistakenly freeze it, we can just introduce
a new function with a different name.

But this is a severe design issue, to introduce new function names. This makes

generic programming impossible. Now the user has to distinguish between

the types, but this is the task of the compiler.

Post by Patrick Walton
Overloading only helps some simple cases, and adds more complexity than it's
worth (IMO).

Overloading is the only way to specialize functions, and this is the only way

to allow generic programming. Without specializing we are back to the bad

old days, where the user has to call the appropriate function for a specific

object, but in a modern programming language the compiler is doing these

things.

Post by Patrick Walton
The problem with C++ isn't that it doesn't have enough features. Rust is
deliberately omitting some features from C++ that don't pull their weight.
Overloading is one of them.

I think that some weights are unavoidable. And I cannot see serious drawbacks

with function overloading, but I see serious drawbacks without:



As I saw Rust the first time, I was impressed, and I decided to overwork the

big integer module (I've already written a big integer library in C), because

the current impementation is much too slow, it suffers from:



1. too many memory allocations

2. some algorithms are a bit naive.



And at first I tried to specialize std::num::pow(), but I gave up immediately,

because I cannot specialize. And without specializing this function I cannot

realize a proper implementation and design, and I'm never doing half-baken

things. So I gave up at all.



The current design in Rust does not allow:



1. Generic programming, in current design of Rust the user has to know,

which function to call for a specific object, and has to use switch (or match)

statements to call it (and if he forget the right functions and uses

std::num::pow(), his program will suffer). This is a programming style 30 years

ago, as I started to write programs.



2. Uniform function signatures, currently the user has to decide about using a

reference or not, but the compiler should decide. If the compiler is deciding,

whether an argument is given by value or by reference, then the problem with

the signature will vanish. And the compiler is better to decide than the user.

One more advantage: the user must not know whether to use a reference

or not when calling a function/method. One exception: a mutable argument, in

this case a reference will be used explicitely by the user, when specifiying

the signature, and when calling the function.



One more drawbacks without overloading: The user defines two print methods:



pub fn print(line : string) -> bool;

pub fn print(line : string, max_line_length : uint) -> bool;



Not possible, he has to use different names. An alternative definition would be:



pub fn print(line : string) -> bool;

pub fn print_with_maxlen(line : string, len : uint) -> bool;



30 years ago this was the normal way, but nowadays, it's a No-Go.



The current status of Rust is: it does not allow proper software design. And

that's bad, because a successor for C++ is needed. Of course, a successor

of C++ does not mean: a better C++. It means, a completely new language

conecept, like Rust. And it does not mean: avoid the good things of C++,

like specialization of functions.



Cheers,

Gregor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/1dc0e055/attachment.html>

[SiegeLordEx]

Post by Gregor Cramer
1. Overloading is not supported (even the archaic C++ is providing this).

I should note that Rust provides a limited form of overloading via the
trait-double dispatch trick:

trait PowImpl<Res>
{
fn pow(self, exp: uint) -> Res;
}

fn pow<Res, T: PowImpl<Res>>(t: T, exp: uint) -> Res
{
t.pow(exp)
}

impl PowImpl<int> for int
{
fn pow(self, exp: uint) -> int
{
...
}
}

impl<'l> PowImpl<BigInt> for &'l BigInt
{
fn pow(self, exp: uint) -> BigInt
{
...
}
}

Note that this is not suitable for generic code, which is kind of an
under-appreciated problem. Currently Rust places running generic code
above writing efficient code, which is not a trade-off it should be
making imo. In my matrix library I opted for making my types useless for
generic code in the quest for efficiency, and I find it unfortunate that
I had to do that.

Post by Gregor Cramer
2. The footprint 'base: T' is not 100% suitable, for big integers the function
definition
fn pow(base: &BigInt, mut exp: uint) -> BigInt
would be more appropriate, because the argument 'base' needs not to be
modified (or reassigned), and a call by reference (avoiding a superfluous
memory allocation) is more efficient in this case.

Yes, I concur on most of these points and I've brought up some related
points before. The operator overloading technique used by Rust is
antithetical to efficient generic code. The core numeric traits and
functions are currently designed only with built-in types in mind,
causing BigInt (and others, e.g. matrices) to suffer. I don't know how
to fix these things, but perhaps auto-ref and ad-hoc operator
overloading (it works for Haskell, why not for Rust?) would be part of
the solution. Ultimately, I suspect that function overloading (the Rust
trait double-dispatch trick above may be sufficient with auto-ref) will
be of critical importance. This problem is very under-appreciated and I
hope this aspect of the language is not stabilized by 1.0.

If the relevant operator overload is removed from BigInt, then one
temporary solution will emerge: you won't be able to call this pow
function at all, and will be forced to call a specialized version. As
long as the core is designed for built-in types only, BigInt should stop
pretending to be one. I think this is what should be done in the interim.

-SL

[Patrick Walton]

Post by SiegeLordEx
Yes, I concur on most of these points and I've brought up some related
points before. The operator overloading technique used by Rust is
antithetical to efficient generic code. The core numeric traits and
functions are currently designed only with built-in types in mind,
causing BigInt (and others, e.g. matrices) to suffer. I don't know how
to fix these things, but perhaps auto-ref and ad-hoc operator
overloading (it works for Haskell, why not for Rust?) would be part of
the solution.

Neither auto-ref or ad-hoc operator overloading would let you write a
generic function that calls `pow` and works optimally with both bigints
and ints. I think the only thing that would work is something like C++
ad-hoc templates, which is a road I don't want to go down.

Post by SiegeLordEx
Ultimately, I suspect that function overloading (the Rust
trait double-dispatch trick above may be sufficient with auto-ref) will
be of critical importance. This problem is very under-appreciated and I
hope this aspect of the language is not stabilized by 1.0.

I don't think we should be trying to solve it.

Patrick

[Josh Haberman]

Post by Patrick Walton
Neither auto-ref or ad-hoc operator overloading
would let you write a generic function that calls
`pow` and works optimally with both bigints and
ints. I think the only thing that would work is
something like C++ ad-hoc templates, which is
a road I don't want to go down.

Could you explain what you mean by "ad-hoc templates", and how this
differs from Rust's templates?

[Patrick Walton]

Post by Josh Haberman

Post by Patrick Walton
Neither auto-ref or ad-hoc operator overloading
would let you write a generic function that calls
`pow` and works optimally with both bigints and
ints. I think the only thing that would work is
something like C++ ad-hoc templates, which is
a road I don't want to go down.

Could you explain what you mean by "ad-hoc templates", and how this
differs from Rust's templates?

In Rust you can never have type errors during template expansion. If a
call to a generic/template typechecks properly, then the template is
guaranteed to expand to valid Rust code with no type errors within it.
This is done via the trait system, which is similar in spirit to the
concept systems proposed for C++17 (the difference being that Rust
*only* has concepts).

The primary benefit of this setup is that the infamous template error
messages in C++ are eliminated. There are a bunch of other secondary
benefits as well: there is no need for the ADL hack, you can do things
like overload on the return type, etc.

Patrick

[Josh Haberman]

On Fri, Jul 25, 2014 at 10:34 AM, Patrick Walton <pcwalton at mozilla.com>

Post by Patrick Walton

Post by Josh Haberman

Post by Patrick Walton
Neither auto-ref or ad-hoc operator overloading
would let you write a generic function that calls
`pow` and works optimally with both bigints and
ints. I think the only thing that would work is
something like C++ ad-hoc templates, which is
a road I don't want to go down.

Could you explain what you mean by "ad-hoc templates", and how this
differs from Rust's templates?

In Rust you can never have type errors during template expansion. If a
call to a generic/template typechecks properly, then the template is
guaranteed to expand to valid Rust code with no type errors within it. This
is done via the trait system, which is similar in spirit to the concept
systems proposed for C++17 (the difference being that Rust *only* has
concepts).

Got it. So the "ad hoc" part refers to having a template parameter, but not
being able to check its capabilities/interface at template
parsing/typechecking time, it sounds like?

How does the trait/concept approach preclude template specialization? Each
template specialization could be independently type-checked, but the most
specialized one could be selected at instantiation time. Or is this
considered "overloading" and discarded because of the extra complexity? I
guess it could be complicated to define which was "most specialized."
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/dec7e02b/attachment.html>

[Patrick Walton]

Post by Josh Haberman
Got it. So the "ad hoc" part refers to having a template parameter, but
not being able to check its capabilities/interface at template
parsing/typechecking time, it sounds like?

Right. (The term comes from "Making Ad-Hoc Polymorphism Less Ad-Hoc",
which is the seminal paper on typeclasses.)

Post by Josh Haberman
How does the trait/concept approach preclude template specialization?
Each template specialization could be independently type-checked, but
the most specialized one could be selected at instantiation time. Or is
this considered "overloading" and discarded because of the extra
complexity? I guess it could be complicated to define which was "most
specialized."

Yeah, that's the complexity. Some GHC language extensions do allow
something like template specialization, but it's considered very
experimental. I'd like to see if things like associated types get us
most of the way there without the difficulties of specialization.

Patrick

[SiegeLordEx]

Post by Patrick Walton
I don't think we should be trying to solve it.

I don't agree. If this problem is truly appreciated, then you have to
conclude that completely generic code is not possible in Rust, which
means that Rust should not bless particular generic signatures (the
operator overloading traits, the iterator trait, maybe a few others I
can't think of right now) with special syntax because they can't
possibly be efficient in all cases.

While this doesn't matter for the pow function (the alternate function
would just have a different path/name), it matters for the special
syntaxes. When the Iterator is no longer enough for you (there was a
case like this in IRC recently involving mutable windows), then you have
to abandon the for loop which is a big syntactic change (right now it
works because it is ad-hoc). Similarly, when the operator overloading
traits are insufficient, then you have to abandon that sugar as well.
One might say "well, don't use those traits then" but that's not what
happens in practice. In practice, people want the syntax sugar and
therefore are guided into inefficiency. Some of BigNum's operator
overloads shouldn't exist because they are so inefficient, and yet they
do because people expect BigNum to act (on a syntactic level) just like
any other number.

So I think this is a real problem with real solutions that don't require
going down the ad-hoc template black hole. Part of the solution has to
involve changing how the language syntax sugar works. The other part,
however, involves libraries: if the generic functions in libnum expect
types to act as built-in types (by requiring T: Mul<T, T> etc), then
BigNum should not act like a built in type; alternatively, the generic
functions in libnum should be overloadable (via the double-dispatch
trick). Maybe there's some other library-based pattern that would work
as well.

-SL

[Patrick Walton]

Post by SiegeLordEx
While this doesn't matter for the pow function (the alternate function
would just have a different path/name), it matters for the special
syntaxes. When the Iterator is no longer enough for you (there was a
case like this in IRC recently involving mutable windows), then you have
to abandon the for loop which is a big syntactic change (right now it
works because it is ad-hoc).

As of last week it's not anymore.

Post by SiegeLordEx
Similarly, when the operator overloading
traits are insufficient, then you have to abandon that sugar as well.
One might say "well, don't use those traits then" but that's not what
happens in practice. In practice, people want the syntax sugar and
therefore are guided into inefficiency. Some of BigNum's operator
overloads shouldn't exist because they are so inefficient, and yet they
do because people expect BigNum to act (on a syntactic level) just like
any other number.
So I think this is a real problem with real solutions that don't require
going down the ad-hoc template black hole.

Well, part of the problem here is that people are going to want to write
generic functions that take addable values. If we start making `+` and
friends overloadable/ad-hoc, then people are going to be surprised when
they can't pass (say) bignums to functions that want addable things.

Patrick

[SiegeLordEx]

Post by Patrick Walton
Well, part of the problem here is that people are going to want to write
generic functions that take addable values. If we start making `+` and
friends overloadable/ad-hoc, then people are going to be surprised when
they can't pass (say) bignums to functions that want addable things.

The current Rust doesn't allow a complete lack of surprise. Either you
will be surprised by the traits not being supported by every numeric
type, or you will be surprised by the terrible performance of most types
that implement Op<T, T>. The core issue is that 'addable' (and other
concepts/functions) cannot be expressed efficiently for all types in
some unified way.

-SL

[Daniel Micay]

Post by Patrick Walton

Post by SiegeLordEx
While this doesn't matter for the pow function (the alternate function
would just have a different path/name), it matters for the special
syntaxes. When the Iterator is no longer enough for you (there was a
case like this in IRC recently involving mutable windows), then you have
to abandon the for loop which is a big syntactic change (right now it
works because it is ad-hoc).

As of last week it's not anymore.

Post by SiegeLordEx
Similarly, when the operator overloading
traits are insufficient, then you have to abandon that sugar as well.
One might say "well, don't use those traits then" but that's not what
happens in practice. In practice, people want the syntax sugar and
therefore are guided into inefficiency. Some of BigNum's operator
overloads shouldn't exist because they are so inefficient, and yet they
do because people expect BigNum to act (on a syntactic level) just like
any other number.
So I think this is a real problem with real solutions that don't require
going down the ad-hoc template black hole.

Well, part of the problem here is that people are going to want to write
generic functions that take addable values. If we start making `+` and
friends overloadable/ad-hoc, then people are going to be surprised when
they can't pass (say) bignums to functions that want addable things.
Patrick

We can start out with efficient generic code for bignums (meaning stuff
like `op(&mut tmp, &a, &b)` in a loop with a reused temporary variable)
and then add a "static" branch + other code for primitives as vector
iterators already do for zero-size types. Ideally there would be a way
of expressing it without relying on optimizations to remove a branch but
the language is expressive enough other than that.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140726/586146f4/attachment.sig>

[Ariel Ben-Yehuda]

std::num::pow is not the most general exponentiation function but a
second-rate utility function in the standard library - you don't have to
use it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140727/d43c44c2/attachment.html>

[Ariel Ben-Yehuda]

[The previous message got sent accidentally by gmail]

However, for performance reasons, I think some kind of trait overloading
would be nice.

i.e., you should be able to do

impl<T> Trait<T> for A<?> { ... }

overload impl Trait<int> for A<?[int/T]> {
//...
}

And when using (x : Trait<int>) the items in the overload impl will be used
instead of the items in the base impl (note that, except for associated
types, overloaded traits won't participate in name resolution/type checking
- so probably force associated types in the overload to be the same as the
base).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140727/123293e1/attachment.html>

[Paul Nathan]

Gregor,

I think the simple answer is that if your function needs to be broadly
extensible in the future and to have specialization, it needs to be
designed in the trait fashion, per the remarks earlier.

Post by Gregor Cramer
Hello Rust folk!
I am new to Rust, and I have doubts concerning current language concepts.
pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T {
if exp == 1 { base }
else {
let mut acc = one::<T>();
while exp > 0 {
if (exp & 1) == 1 {
acc = acc * base;
}
base = base * base;
exp = exp >> 1;
}
acc
}
}
In general this implementation is ok, but not really usable with BigInt. Of
course, the call ':.std::num::pow(a, 1000)', 'a' is a BigInt, works. But this
implementation is not adequate for big integers. Firstly, too many memory
allocations during the computation (a specialized version can avoid these
memory allocations), secondly, for big integers a specialized function for
squaring (base * base) has to be used, because squaring can be done quite
more efficient than multiplication (with big integers). So this function is much
1. Overloading is not supported (even the archaic C++ is providing this).
2. The footprint 'base: T' is not 100% suitable, for big integers the function
definition
fn pow(base: &BigInt, mut exp: uint) -> BigInt
would be more appropriate, because the argument 'base' needs not to be
modified (or reassigned), and a call by reference (avoiding a superfluous
memory allocation) is more efficient in this case.
Of cource, a specialized version of pow() could be implemented in trait
BigInt, but this is only a workaround. And if a user only knows
::std::num::pow(), he will use an inappropriate implementation without
being aware of this.
Probably in this case it might be a solution to move pow() into a trait,
but
I'm speaking about a general problem. Rust 1.0 will be released, and someone
is developing a new module for version 1.1. But some of the functions in 1.0
are inadequate for the new module, how to solve this without changing the API
in 1.1? I think that function overloading may help in some cases, but the
problem with inappropriate footprints remains. In my opinion this
thing with the footprints (reference or not if the real type is unknown -
that's why the concept with 'const' in C++ exists) is a conceptual design
issue, but probably I do not yet fully understand Rust.
BTW: the functions next_power_of_two(), and checked_next_power_of_two()
are only defined for primitives (trait Primitive), but should also be
applicable for big integers, I think .
C heers,
Gregor
_______________________________________________
Rust-dev mailing list
Rust-dev at mozilla.org
https://mail.mozilla.org/listinfo/rust-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140730/04a69c28/attachment.html>