www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Mixed int/BigInt foreach interval

reply bearophile <bearophileHUGS lycos.com> writes:
In my opinion it's important to make BigInts work in most places where normal
ints work. I think it's even worth modifying D language a bit (if and where
necessary) to allow this.

Time ago I've asked to use BigInt with iota too (no D changes needed here):
http://d.puremagic.com/issues/show_bug.cgi?id=6447
because currently this doesn't work (std.traits.isIntegral needs to change, and
there changes needed in iota too, because it can't use the current
std.traits.unsigned, because a BigInt has no ".min" field):


import std.bigint, std.range;
void main() {
    foreach (i; iota(BigInt(10))) {}
}


Recently I've seen another situation where foreach can't be used in generic
code that works with ints. This useless reduced code shows the situation:


import std.stdio, std.bigint;
void foo(T)(T n) {
    //for (T i = 1; i < n; i++)
    foreach (i; 1 .. n) // line 4
        writeln(i);
}
void main() {
    foo(5);
    foo(BigInt(5));
}


The error given:
test.d(4): Error: incompatible types for ((2) + (n)): 'int' and 'BigInt'


This too doesn't work:

import std.stdio, std.bigint;
void foo(T)(T n) {
    foreach (T i; 1 .. n) // line 3
        writeln(i);
}
void main() {
    foo(BigInt(5));
}


The error:
test.d(3): Error: cannot implicitly convert expression (1) of type int to BigInt


And even this doesn't work:

import std.stdio, std.bigint;
void foo(T)(T n) {
    foreach (i; T(1) .. n) // line 3
        writeln(i);
}
void main() {
    foo(BigInt(5));
}


The error:

...\dmd2\src\phobos\std\traits.d(3312): Error: static assert  "Type BigInt does
not have an Unsigned counterpart"


And the "int(10)" syntax is not supported in D (it is supported in Python).

The sum of int and BigInt is supported, this works:

import std.bigint;
void main() {
    auto x = 1 + BigInt(1);
}



And this too works:

import std.stdio, std.bigint;
void main() {
    foreach (i; BigInt(1) .. BigInt(5))
        writeln(i);
}


That foreach error message looks similar to this type unification error:

import std.bigint;
void main() {
    BigInt x = BigInt(1);
    auto y = true ? 1 : x;
}

test.d(4): Error: incompatible types for ((1) ? (x)): 'int' and 'BigInt'


So is this foreach problem worth fixing? Is it fixable? Is all this fit for
Bugzilla?

Bye, and thank you,
bearophile
Sep 26 2011
next sibling parent reply Paul D. Anderson <paul.d.removethis.anderson comcast.andthis.net> writes:
bearophile Wrote:


 Time ago I've asked to use BigInt with iota too (no D changes needed here):
 http://d.puremagic.com/issues/show_bug.cgi?id=6447
 because currently this doesn't work (std.traits.isIntegral needs to change,
and there changes needed in iota too, because it can't use the current
std.traits.unsigned, because a BigInt has no ".min" field):


Yes, it would be nice to allow isIntegral, isArithmetic, etc. to recognize
library types and not just built-in types.

This would be helpful for, for instance, rational numbers and decimal numbers
(BigDecimal and decimal32, decimal64, decimal128.

As an aside, for those who are interested, the Decimal library implementing the
numbers listed above is very near completion. Just some testing and tidying to
do before it can go on the review queue.

Paul
Sep 26 2011
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, September 26, 2011 13:47 Paul D. Anderson wrote:

 bearophile Wrote:

 Time ago I've asked to use BigInt with iota too (no D changes needed
 here): http://d.puremagic.com/issues/show_bug.cgi?id=6447


 

 because currently this doesn't work (std.traits.isIntegral needs to 




change, and there changes needed in iota too, because it can't use the current 
std.traits.unsigned, because a BigInt has no ".min" field):

 Yes, it would be nice to allow isIntegral, isArithmetic, etc. to recognize
 library types and not just built-in types.
 
 This would be helpful for, for instance, rational numbers and decimal
 numbers (BigDecimal and decimal32, decimal64, decimal128.
 
 As an aside, for those who are interested, the Decimal library implementing
 the numbers listed above is very near completion. Just some testing and
 tidying to do before it can go on the review queue.


I think that we need to be _very_ careful about the implications of making 
isIntegral and other similar traits functions work with non-primitive types. 
There could _easily_ be code which assumes that it's going to get primitive 
types when isIntegral is true. Take the integer swapping code in std.bitmanip. 
It would fail miserably if all of a sudden BigInt worked with isIntegral, and 
you tried to use BigInt with it.

I can see we might want to have isIntegral work with BigInt, but I do _not_ 
think it's necessarily the case that it's actually a good idea. We need to be 
careful about the implications of all of that and make very informed decisions 
about the changes that we make to std.traits, or a lot of code is going to 
break in non-obvious ways.

- Jonathan M Davis
Sep 26 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/26/2011 11:05 PM, Jonathan M Davis wrote:

 On Monday, September 26, 2011 13:47 Paul D. Anderson wrote:

 bearophile Wrote:

 Time ago I've asked to use BigInt with iota too (no D changes needed
 here): http://d.puremagic.com/issues/show_bug.cgi?id=6447



 because currently this doesn't work (std.traits.isIntegral needs to




 change, and there changes needed in iota too, because it can't use the current
 std.traits.unsigned, because a BigInt has no ".min" field):

 Yes, it would be nice to allow isIntegral, isArithmetic, etc. to recognize
 library types and not just built-in types.

 This would be helpful for, for instance, rational numbers and decimal
 numbers (BigDecimal and decimal32, decimal64, decimal128.

 As an aside, for those who are interested, the Decimal library implementing
 the numbers listed above is very near completion. Just some testing and
 tidying to do before it can go on the review queue.


 I think that we need to be _very_ careful about the implications of making
 isIntegral and other similar traits functions work with non-primitive types.
 There could _easily_ be code which assumes that it's going to get primitive
 types when isIntegral is true. Take the integer swapping code in std.bitmanip.
 It would fail miserably if all of a sudden BigInt worked with isIntegral, and
 you tried to use BigInt with it.

 I can see we might want to have isIntegral work with BigInt, but I do _not_
 think it's necessarily the case that it's actually a good idea. We need to be
 careful about the implications of all of that and make very informed decisions
 about the changes that we make to std.traits, or a lot of code is going to
 break in non-obvious ways.

 - Jonathan M Davis


The issue is that isIntegral does not actually check if the data type 
represents integers, it checks if the type is some sort of bit vector 
with two's complement arithmetics defined on it.

Therefore, BigInt should never be included into isIntegral. But I 
totally agree with bearophile that some solution has to be found to make 
BigInt work with generic functions in Phobos.
Sep 26 2011
parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 9/26/11, Timon Gehr <timon.gehr gmx.ch> wrote:

 it checks if the type is some sort of bit vector
 with two's complement arithmetics defined on it.


I thought it's just hardcoded:

template isIntegral(T)
{
    enum bool isIntegral = staticIndexOf!(Unqual!(T), byte,
            ubyte, short, ushort, int, uint, long, ulong) >= 0;
}
Sep 26 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/26/2011 11:46 PM, Andrej Mitrovic wrote:

 On 9/26/11, Timon Gehr<timon.gehr gmx.ch>  wrote:

 it checks if the type is some sort of bit vector
 with two's complement arithmetics defined on it.


 I thought it's just hardcoded:

 template isIntegral(T)
 {
      enum bool isIntegral = staticIndexOf!(Unqual!(T), byte,
              ubyte, short, ushort, int, uint, long, ulong)>= 0;
 }


Yes, of course, that is how it is implemented.
Sep 26 2011
prev sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 9/26/11, Jonathan M Davis <jmdavisProg gmx.com> wrote:

 I think that we need to be _very_ careful about the implications of making
 isIntegral and other similar traits functions work with non-primitive types.
 There could _easily_ be code which assumes that it's going to get primitive
 types when isIntegral is true.


Not *there easily could be* but *there is*. At least in my code..
Sep 26 2011
prev sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, September 26, 2011 14:13 Andrej Mitrovic wrote:

 On 9/26/11, Jonathan M Davis <jmdavisProg gmx.com> wrote:

 I think that we need to be _very_ careful about the implications of
 making isIntegral and other similar traits functions work with
 non-primitive types. There could _easily_ be code which assumes that
 it's going to get primitive types when isIntegral is true.


 
 Not *there easily could be* but *there is*. At least in my code..


What I probably meant to say was "Code could easily assume that..." but you 
get the idea. Certainly, there's no question that there's code out there that 
would be broken by such a change - including code in Phobos. So, we need to be 
very careful about any such changes. But since it would be easy to have a 
template constraint check

if(isIntegral!T || is(Unqual!T == BigInt))

I don't see much benefit in making isIntegral return true for BigInt anyway. 
BigInt is _not_ the same as the built-in integral types. Code which uses
integral types could easily not work with BigInt. Yes, there is plenty of code
that could work with both, but it needs to be designed with that level of 
genericness in mind, and much of the code using isIntegral is _not_.

- Jonathan M Davis
Sep 26 2011
parent reply Mehrdad <wfunction hotmail.com> writes:
On 9/26/2011 2:25 PM, Jonathan M Davis wrote:

 What I probably meant to say was "Code could easily assume that..." 
 but you get the idea. Certainly, there's no question that there's code 
 out there that would be broken by such a change - including code in 
 Phobos. So, we need to be very careful about any such changes. But 
 since it would be easy to have a template constraint check 
 if(isIntegral!T || is(Unqual!T == BigInt)) I don't see much benefit in 
 making isIntegral return true for BigInt anyway. BigInt is _not_ the 
 same as the built-in integral types. Code which uses integral types 
 could easily not work with BigInt. Yes, there is plenty of code that 
 could work with both, but it needs to be designed with that level of 
 genericness in mind, and much of the code using isIntegral is _not_. - 
 Jonathan M Davis 


IMHO that's a pretty bad constraint check.

What it should instead be is something along the lines of:

isIntegral!T && isPrimitive!T
Sep 26 2011
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, September 26, 2011 18:33:22 Mehrdad wrote:

 On 9/26/2011 2:25 PM, Jonathan M Davis wrote:

 What I probably meant to say was "Code could easily assume that..."
 but you get the idea. Certainly, there's no question that there's code
 out there that would be broken by such a change - including code in
 Phobos. So, we need to be very careful about any such changes. But
 since it would be easy to have a template constraint check
 if(isIntegral!T || is(Unqual!T == BigInt)) I don't see much benefit in
 making isIntegral return true for BigInt anyway. BigInt is _not_ the
 same as the built-in integral types. Code which uses integral types
 could easily not work with BigInt. Yes, there is plenty of code that
 could work with both, but it needs to be designed with that level of
 genericness in mind, and much of the code using isIntegral is _not_. -
 Jonathan M Davis


 
 IMHO that's a pretty bad constraint check.
 
 What it should instead be is something along the lines of:
 
 isIntegral!T && isPrimitive!T


Why is it bad? isIntegral was specifically designed for testing that a type was 
one of byte, ubyte, short, ushort, int, uint, long, and ulong, and that's 
exactly what it's doing.

- Jonathan M Davis
Sep 26 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 Why is it bad? isIntegral was specifically designed for testing that a type
was 
 one of byte, ubyte, short, ushort, int, uint, long, and ulong, and that's 
 exactly what it's doing.


Going back to my original post, is changing the semantics of isIntegral enough
to allow code like this to compile and run?

foreach (i; 1 .. BigInt(10)) {}

Bye,
bearophile
Sep 26 2011
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, September 26, 2011 21:49:49 bearophile wrote:

 Jonathan M Davis:

 Why is it bad? isIntegral was specifically designed for testing that a
 type was one of byte, ubyte, short, ushort, int, uint, long, and ulong,
 and that's exactly what it's doing.


 
 Going back to my original post, is changing the semantics of isIntegral
 enough to allow code like this to compile and run?
 
 foreach (i; 1 .. BigInt(10)) {}


No. That's foreach. BigInt isn't going to work with the .. syntax regardless 
of what isIntegral does. I assume what you're really asking is whether

foreach(i; iota(1, BigInt(10))) {}

would work. And the answer is definitely no. iota is too complex for simply 
changing isIntegral to work. For instance, CommonType would fail, because 
BigInt and int are not implicitly convertible between one another. I'm sure 
that iota could be reworked such that it could work with BigInt and work with 
a combination of int and BigInt, but it's definitely not as simple as simply 
messing around with the template constraint.

- Jonathan M Davis
Sep 26 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 foreach (i; 1 .. BigInt(10)) {}


 
 No. That's foreach. BigInt isn't going to work with the .. syntax regardless 
 of what isIntegral does. I assume what you're really asking is whether


I'm asking about foreach, not about iota. Fixing iota is easy, it's just a
matter of changing Phobos.

This is why at the top of my original post I have written:


 In my opinion it's important to make BigInts work in most places where normal
ints work.
 I think it's even worth modifying D language a bit (if and where necessary) to
allow this.


The point of my post was to talk about foreach. The title of this thread is
"Mixed int/BigInt foreach interval".

Bye,
bearophile
Sep 27 2011
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, September 27, 2011 12:22 bearophile wrote:

 Jonathan M Davis:

 foreach (i; 1 .. BigInt(10)) {}


 
 No. That's foreach. BigInt isn't going to work with the .. syntax
 regardless of what isIntegral does. I assume what you're really asking
 is whether


 
 I'm asking about foreach, not about iota. Fixing iota is easy, it's just a
 matter of changing Phobos.
 
 This is why at the top of my original post I have written:

 In my opinion it's important to make BigInts work in most places where
 normal ints work. I think it's even worth modifying D language a bit (if
 and where necessary) to allow this.


 
 The point of my post was to talk about foreach. The title of this thread is
 "Mixed int/BigInt foreach interval".


I'd be _very_ surprised to see that happen, since BigInt is in Phobos as 
opposed to being at the language level. Ranges could be added to foreach, 
because they're entirely API-based, and so the compiler doesn't have to care 
about what Phobos is doing. It just has to do the appropriate lowerings. But 
BigInt is a specific type in Phobos. Making it work with foreach would mean 
that the compiler would have to know and understand about BigInt. I don't 
expect that to ever happen. Best case, I would think that you could get it to 
work by having BigInt be implicitly convertible to int, but since that's a 
narrowing conversion, that's a _bad_ idea IMHO.

- Jonathan M Davis
Sep 27 2011
next sibling parent reply kennytm <kennytm gmail.com> writes:
"Jonathan M Davis" <jmdavisProg gmx.com> wrote:

 On Tuesday, September 27, 2011 12:22 bearophile wrote:

 Jonathan M Davis:

 foreach (i; 1 .. BigInt(10)) {}


 
 No. That's foreach. BigInt isn't going to work with the .. syntax
 regardless of what isIntegral does. I assume what you're really asking
 is whether


 
 I'm asking about foreach, not about iota. Fixing iota is easy, it's just a
 matter of changing Phobos.
 
 This is why at the top of my original post I have written:

 In my opinion it's important to make BigInts work in most places where
 normal ints work. I think it's even worth modifying D language a bit (if
 and where necessary) to allow this.


 
 The point of my post was to talk about foreach. The title of this thread is
 "Mixed int/BigInt foreach interval".


 
 I'd be _very_ surprised to see that happen, since BigInt is in Phobos as 
 opposed to being at the language level. Ranges could be added to foreach, 
 because they're entirely API-based, and so the compiler doesn't have to care 
 about what Phobos is doing. It just has to do the appropriate lowerings. But 
 BigInt is a specific type in Phobos. Making it work with foreach would mean 
 that the compiler would have to know and understand about BigInt. I don't 
 expect that to ever happen. Best case, I would think that you could get it to 
 work by having BigInt be implicitly convertible to int, but since that's a 
 narrowing conversion, that's a _bad_ idea IMHO.
 
 - Jonathan M Davis


foreach (a; b .. c) d;   is also a lowering, and i'd say the 'int + BigInt'
not able to typeCombine (statement.c:2282) a bug.

By the way, the statement

    foreach (a; BigInt(1) .. 10) ...

does compile and work, at least for the toolset from git master.
Sep 27 2011
parent bearophile <bearophileHUGS lycos.com> writes:
kennytm:


 foreach (a; b .. c) d;   is also a lowering, and i'd say the 'int + BigInt'
 not able to typeCombine (statement.c:2282) a bug.
 
 By the way, the statement
 
     foreach (a; BigInt(1) .. 10) ...
 
 does compile and work, at least for the toolset from git master.


Thank you for your answer. This was the real topic of my original post :-)
Sorry for the confusion.

Bye,
bearophile
Sep 27 2011
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
It seems my original post of this thread was confused and not clear enough. In
that post I have also mixed two different things (a Phobos enhancement request
that doesn't require a lot of discussion, and a more complex discussion about
usefulness of possible D language changes. See below).


Jonathan M Davis:


 I'd be _very_ surprised to see that happen, since BigInt is in Phobos as 
 opposed to being at the language level.


Multi-precision integers are important. In several languages they are even
built-in (like in Lisp/Scheme languages, Haskell, Python, some modern variants
of Forth, and so on).

I didn't ask to turn BigInts into D built-ins. What I was asking is if there
are generic ideas worth changing in D language to allow a better creation and
integration of library-defined multi-precision integers :-) (example: ideas
like opCast(bool) are not specific to BigInts, but they allow to implement
better BigInts).
Maybe there are no ways to improve the situation.

Bye,
bearophile
Sep 27 2011
prev sibling parent reply travert phare.normalesup.org (Christophe) writes:
Jonathan M Davis , dans le message (digitalmars.D:145520), a écrit :

 foreach (i; 1 .. BigInt(10)) {}


 
 BigInt isn't going to work with the .. syntax regardless of what 
 isIntegral does.


It makes some time that I think the .. syntax should be improved.
I wanted to make a post about that but I have done it yet.

First, Range are such a part of the langage now that I think 0..10 
deserves to be a Range, and not a syntax sugar for opSlice and foreach. 

It could be a type called int..int that behaves like iota!(int, int), 
and .. be an operator that takes for example two ints and return an 
int..int(*).

| auto OpSlice(size_t, size_t);
could be renamed
| auto OpIndex(size_t..size_t);
and we could also make overloads for multidimensional arrays:
| auto OpIndex(size_t..size_t, size_t..size_t);
which is IMHO much more meaningful and satisfying than:
| auto OpIndex(size_t, size_t, size_t, size_t);
or
| auto OpSlice(size_t[2], size_t[2]);

People might say this makes the langage more complicated, because we 
create a new type in the language. I think on the contrary that this 
makes the language simpler: it unifies foreach(i; 1..n),
opSlice(size_t, size_t), opIndex (and iota in many cases).

-- 
Christophe

(*) Notes:
- compose type like char..int should be forbidden in a way. In 
char a; a..1000, the char a should be promoted to int to make an 
int..int.

- the .. operator could be overloaded for types like BigInt, like normal 
binary operator overloads. This overload may returned a user-defined 
type (that we ask to be a Range), or, alternatively, the langage could 
allow to have a BigInt..BigInt type, with the library being able to 
overload operations (empty, front, popFront, etc) on BigInt..BigInt like 
we can do for arrays (like: popFront(BigInt..BigInt r) { r[0] = r[0] + 
1; } ).
Sep 28 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/28/2011 03:33 PM, Christophe wrote:

 Jonathan M Davis , dans le message (digitalmars.D:145520), a écrit :

 foreach (i; 1 .. BigInt(10)) {}


 BigInt isn't going to work with the .. syntax regardless of what
 isIntegral does.


 It makes some time that I think the .. syntax should be improved.
 I wanted to make a post about that but I have done it yet.

 First, Range are such a part of the langage now that I think 0..10
 deserves to be a Range, and not a syntax sugar for opSlice and foreach.

 It could be a type called int..int that behaves like iota!(int, int),
 and .. be an operator that takes for example two ints and return an
 int..int(*).

 | auto OpSlice(size_t, size_t);
 could be renamed
 | auto OpIndex(size_t..size_t);
 and we could also make overloads for multidimensional arrays:
 | auto OpIndex(size_t..size_t, size_t..size_t);
 which is IMHO much more meaningful and satisfying than:
 | auto OpIndex(size_t, size_t, size_t, size_t);
 or
 | auto OpSlice(size_t[2], size_t[2]);

 People might say this makes the langage more complicated, because we
 create a new type in the language. I think on the contrary that this
 makes the language simpler: it unifies foreach(i; 1..n),
 opSlice(size_t, size_t), opIndex (and iota in many cases).


This would probably be a breaking language change, because currently 
'..' has no operator precedence associated with it (it is just a 
delimiter token, much like ';').

 Topic: In practice, I have never felt the need to use BigInt's as 
foreach iterator variables. What is the use for such a feature?

I mean, eg. the following is hardly useful:

foreach(i;0..BigInt("10000000000000000000000000"){}
Sep 28 2011
next sibling parent travert phare.normalesup.org (Christophe) writes:
Timon Gehr , dans le message (digitalmars.D:145614), a écrit :

 This would probably be a breaking language change, because currently 
 '..' has no operator precedence associated with it (it is just a 
 delimiter token, much like ';').


If by breaking language change, you mean that this would break existing 
code, I don't think so. if we exclude the ugly case:..case: syntax, a..b 
can only be found between ; or ( and ), so there is no precedence issue 
if the precedence is low enough (although a too low precedence might not 
be the best place...). By the way, is there some place we can find 
operator's precedence in D?

Anyway, I guess introducing this change would imply a lot of work, that 
has no real priority. But it's worth giving it a thought.


  Topic: In practice, I have never felt the need to use BigInt's as 
 foreach iterator variables. What is the use for such a feature?
 
 I mean, eg. the following is hardly useful:
 
 foreach(i;0..BigInt("10000000000000000000000000"){}


The copy on write behavior of BigInt makes it very poorly efficient 
to iterate on. In addition, I guess the compiler won't be able to 
optimize anything. Someone could say this is a good reason to make the 
.. syntax on BigInt harder to use.

-- 
Christophe
Sep 28 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Timon Gehr:


 I mean, eg. the following is hardly useful:
 
 foreach(i;0..BigInt("10000000000000000000000000"){}


I'd like a function template like this to work even if T is BigInt:

T binomial(T)(T n, T k) {
    if (k > n/2)
        k = n - k;
    T bc = n - k + 1;
    foreach (i; 2 .. k+1)
        bc = (bc * (n - k + i)) / i;
    return bc;
}


Current workaround: use this instead of the foreach:
for (T i = 2; i <= k; i++)

----------------------------

Christophe:


 The copy on write behavior of BigInt makes it very poorly efficient
 to iterate on. In addition, I guess the compiler won't be able to
 optimize anything. Someone could say this is a good reason to make the
 .. syntax on BigInt harder to use.


I'd like to use BigInts often in D. So some compiler optimizations are welcome
here.

Bye,
bearophile
Sep 28 2011
parent reply travert phare.normalesup.org (Christophe) writes:
bearophile , dans le message (digitalmars.D:145640), a écrit :

 Timon Gehr:
 

 I mean, eg. the following is hardly useful:
 
 foreach(i;0..BigInt("10000000000000000000000000"){}


 
 I'd like a function template like this to work even if T is BigInt:
 
 T binomial(T)(T n, T k) {
     if (k > n/2)
         k = n - k;
     T bc = n - k + 1;
     foreach (i; 2 .. k+1)
         bc = (bc * (n - k + i)) / i;
     return bc;
 }
 
 
 Current workaround: use this instead of the foreach:
 for (T i = 2; i <= k; i++)


That seems to be a very reasonable workarround.
Does
foreach(i; (cast(T) 2) .. k+1) work ?


 Christophe:
 

 The copy on write behavior of BigInt makes it very poorly efficient
 to iterate on. In addition, I guess the compiler won't be able to
 optimize anything. Someone could say this is a good reason to make the
 .. syntax on BigInt harder to use.


 
 I'd like to use BigInts often in D. So some compiler optimizations are welcome
here.


BigInt is in the library, not in the language. I hardly see a way the 
compiler could optimize this. At the best, it could recognise that the 
BigInt is wasted at the end of each iteration and destroy/reuse it's 
content right away. Reusing can be hard, since the size of the BigInt 
can get bigger.

The best way to optimize this is at the library level.
Eventually, since iota and BigInt are in the same library, iota could 
provided an overload for BigInt that uses a kind of mutable BigInt. 

BigInt reused the Python idiom of immutable data and copy-on-write. I am 
not sure this is such a good idea in D, where the garbage collector is 
different, types are not all supposed to be immutable, and the 
performance expectations are higher, and optimization opportunities are 
different.

-- 
Christophe
Sep 29 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Christophe:


 That seems to be a very reasonable workarround.
 Does
 foreach(i; (cast(T) 2) .. k+1) work ?


It seems to work. It is a variant I have not tried. Thank you. But probably
I'll write a low-priority enhancement request any way.



 BigInt is in the library, not in the language. I hardly see a way the 
 compiler could optimize this.


The threshold between compiler and library is not fully sharp. Complex numbers
will become fully library types. Associative arrays are mostly defined in D
code, they have literals defined in the language. Both of them have changed
their position. Hopefully D2 will add some syntax sugar to manage tuples a bit
better (for their unpacking, mostly). So there are movements in both directions.

Bye,
bearophile
Sep 29 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/26/11 6:49 PM, bearophile wrote:

 Jonathan M Davis:


 Why is it bad? isIntegral was specifically designed for testing that a type was
 one of byte, ubyte, short, ushort, int, uint, long, and ulong, and that's
 exactly what it's doing.


 Going back to my original post, is changing the semantics of isIntegral enough
to allow code like this to compile and run?

 foreach (i; 1 .. BigInt(10)) {}

 Bye,
 bearophile


Well isIntegral was designed indeed for primitive integral types. The 
problem with having isIntegral!BigInt dilutes the meaning of isIntegral 
because there are significant differences between

Without having thought a lot of this, my impression is we need a sort of 
isMonoid!(T, "+", 0) as a guard for iota.


Andrei
Sep 26 2011
parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 27/09/11 3:06 AM, Andrei Alexandrescu wrote:

 On 9/26/11 6:49 PM, bearophile wrote:

 Jonathan M Davis:


 Why is it bad? isIntegral was specifically designed for testing that
 a type was
 one of byte, ubyte, short, ushort, int, uint, long, and ulong, and
 that's
 exactly what it's doing.


 Going back to my original post, is changing the semantics of
 isIntegral enough to allow code like this to compile and run?

 foreach (i; 1 .. BigInt(10)) {}

 Bye,
 bearophile


 Well isIntegral was designed indeed for primitive integral types. The
 problem with having isIntegral!BigInt dilutes the meaning of isIntegral
 because there are significant differences between

 Without having thought a lot of this, my impression is we need a sort of
 isMonoid!(T, "+", 0) as a guard for iota.


 Andrei


I think this is the best route, although it is unfortunate that 
is*Integral* fails on Big*Integer*. If an integer isn't integral then I 
don't know what is :-)

isIntegral should have been called isIntegralPrimitive or 
isMachineInteger or something along those lines if that was what it was 
designed for. I guess it's too late for that now.

Or could it be deprecated then re-purposed at the end of the deprecation 
period?
Sep 27 2011
prev sibling parent reply "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Tue, 27 Sep 2011 03:38:11 +0200, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:


 isIntegral was specifically designed for testing that a type was
 one of byte, ubyte, short, ushort, int, uint, long, and ulong, and that's
 exactly what it's doing.


The name indicates it checks for generic integral-ness, not for built-in  
types.

Given that changing isIntegral is likely to break a lot of code (is it?),
perhaps we should also add behavesLikeIntegral, which checks for behavior
instead of concrete types.

-- 
   Simen
Sep 26 2011
parent Don <nospam nospam.com> writes:
On 27.09.2011 04:08, Simen Kjaeraas wrote:

 On Tue, 27 Sep 2011 03:38:11 +0200, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:


 isIntegral was specifically designed for testing that a type was
 one of byte, ubyte, short, ushort, int, uint, long, and ulong, and that's
 exactly what it's doing.


 The name indicates it checks for generic integral-ness, not for built-in
 types.

 Given that changing isIntegral is likely to break a lot of code (is it?),
 perhaps we should also add behavesLikeIntegral, which checks for behavior
 instead of concrete types.


Well, actually BigInt behaves like an integer, unlike the built-in 
types, which don't <g>.

BigInt and the built-ins have quite different semantics. But there is 
also a substantial overlap. We definitely need some generic check for 
that common subset of functionality.
Another interesting case is a FixedLengthInt, which follows the same 
arithmetic as the built-in types, but isn't built-in.
Sep 26 2011