www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4085] New: Steps toward a static foreach

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085

           Summary: Steps toward a static foreach
           Product: D
           Version: future
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



A "static foreach" can be useful to statically unroll loops (both on a small
numerical range, or for example on items of an array/matrix known at compile
time, this can significantly improve the performance of some code), to define
many switch cases in a compact way, to reduce code duplication using string
mixins, and so on. It can be useful both inside and outside function bodies.

Currently the foreach on tuples is static, but the new D programmer can ignore
this, and a quick inspection of D code doesn't tell if a foreach is static or
runtime. Generally in D code it's important to always be able to visually tell
apart static statements (like static if, static assert) from their runtime
variants. 

At the moment it's possible to use a limited form of static foreach on a
numeric range, using a helper template like (similar Range can be defined with
one and three input arguments):

template Range(int start, int stop) {
    static if (stop <= start)
        alias Tuple!() Range;
    else
        alias Tuple!(Range!(start, stop-1), stop-1) Range;
}

But Range generates many templates, works only inside functions, and visually
the code that uses Range!() is not visually distinct from the runtime foreach.


Andrei has commented:

 static foreach was part of the plan until recently, but Walter
 encountered severe implementation difficulties so we had to abandon it.
 I agree that it's odd that the same statement iterates at compile-time
 or run-time depending on the iterated type.


I'd like Walter to explain why it's hard to implement, maybe some other
programmer can find a way to implement it.

Even if a static foreach can't be fully implemented, there are other
intermediate solutions. Even a partially implemented static foreach is an
improvement over the current situation. There are various levels of
implementation of static foreach, more and more complete, each one of them is
better than the last one:

1) Just require the prefix keyword "static" before "foreach" when the foreach
is done on a tuple. This doesn't change the semantics of the current D
programs, but helps who will read the D code to visually tell apart the static
case from the runtime case. I think this is not too much hard to implement.

2) The compiler can translate (lower) code like "static foreach (i; 10 .. 20)"
into something like that "static foreach (i; Range!(10, 20))", using a Range
template defined automatically (this static foreach on a range can be used only
inside functions).

3) The same as point (2), but the compiler can avoid instantiating all those
templates. This can reduce memory used during compilation and speed up the
compilation a little.

4) The same as (3) but it can work on arrays too known at compile time too. The
compiler can convert arrays known at compile time into tuples, and then iterate
on a numerical range as long as the array, and pick items from the tuple usign
an index. (This is already doable now, with a recursive template that converts
an array known at compile time into a tuple).

5) Like (4) but the compiler can optimize better, avoiding the conversion from
the array known at compile time into a tuple (as the precedent levels, this
static foreach can be used only inside functions).

6) This is the full static foreach, that can be used outside the body of any
function too.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 12 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085




// Until bug 4085 gets fixed, I use something similar to this.
// I suggest to not add this to Phobos because it
//   will become useless when bug 4085 is partially of fully fixed.



import std.typetuple: TypeTuple;
import std.traits: isArray;

version(unittest) {
    import std.string: split; // for arrayToTypeTuple!() unittests
}

/****************************************
Converts at compile time an enum array into a TypeTuple that
contains the same items.

Example:
--------
foreach (i; arrayToTypeTuple!([1, 2]))
    static assert(i > 0);
--------
*/
template arrayToTypeTuple(alias items) {
    static assert (isArray!(typeof(items)));
    static if (items == null || items.length == 0) // bug 4284
        alias TypeTuple!() arrayToTypeTuple;
    else
        alias TypeTuple!(items[0], arrayToTypeTuple!(items[1..$]))
arrayToTypeTuple;
}

unittest { // Tests of arrayToTypeTuple!()
    string[] items;
    foreach (s; arrayToTypeTuple!(split(""))) {
        static assert(s.length > 0);
        items ~= s;
    }
    assert(items.length == 0);

    items.length = 0;
    foreach (s; arrayToTypeTuple!(split("foo"))) {
        static assert(s.length > 0);
        items ~= s;
    }
    assert(items == ["foo"]);

    items.length = 0;
    foreach (s; arrayToTypeTuple!(split("foo bar red"))) {
        static assert(s.length > 0);
        items ~= s;
    }
    assert(items == ["foo", "bar", "red"]);

    foreach (i; arrayToTypeTuple!([1, 2]))
        static assert(i > 0);
} // End tests of arrayToTypeTuple!()



/****************************************
Template, similar to iota(), but generates a tuple at compile time.

Useful for "static foreach" loops, where range extrema are compile time
constants:
-----------
foreach (i; Iota!(3))
    a[i] = b[i];

// becomes unrolled and compiled as:
    a[0] = b[0];
    a[1] = b[1];
    a[2] = b[2];
-----------
*/
template Iota(int stop) {
    static if (stop <= 0)
        alias TypeTuple!() Iota;
    else
        alias TypeTuple!(Iota!(stop-1), stop-1) Iota;
}

/// ditto
template Iota(int start, int stop) {
    static if (stop <= start)
        alias TypeTuple!() Iota;
    else
        alias TypeTuple!(Iota!(start, stop-1), stop-1) Iota;
}

/// ditto
template Iota(int start, int stop, int step) {
    static assert(step != 0, "Iota: step must be != 0");

    static if (step > 0) {
        static if (stop <= start)
            alias TypeTuple!() Iota;
        else
            alias TypeTuple!(Iota!(start, stop-step, step), stop-step) Iota;
    } else {
        static if (stop >= start)
            alias TypeTuple!() Iota;
        else
            alias TypeTuple!(Iota!(start, stop-step, step), stop-step) Iota;
    }
} // End Iota!(a,b,c)

unittest { // Tests of Iota!()
    static assert(Iota!(0).length == 0);

    int[] a;

    foreach (n; Iota!(5))
        a ~= n;
    assert(a == [0, 1, 2, 3, 4]);

    a.length = 0;
    foreach (n; Iota!(-5))
        a ~= n;
    assert(a == new int[0]);

    a.length = 0;
    foreach (n; Iota!(4, 7))
        a ~= n;
    assert(a == [4, 5, 6]);

    a.length = 0;
    foreach (n; Iota!(-1, 4))
        a ~= n;
    static assert(Iota!(-1, 4).length == 5);
    assert(a == [-1, 0, 1, 2, 3]);

    a.length = 0;
    foreach (n; Iota!(4, 2))
        a ~= n;
    assert(a == new int[0]);

    a.length = 0;
    foreach (n; Iota!(0, 10, 2))
        a ~= n;
    assert(a == [0, 2, 4, 6, 8]);

    a.length = 0;
    foreach (n; Iota!(3, 15, 3))
        a ~= n;
    assert(a == [3, 6, 9, 12]);

    a.length = 0;
    foreach (n; Iota!(15, 3, 1))
        a ~= n;
    assert(a == new int[0]);

    a.length = 0;
    foreach (n; Iota!(10, 0, -1))
        a ~= n;
    assert(a == [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]);

    a.length = 0;
    foreach (n; Iota!(15, 3, -2))
        a ~= n;
    assert(a == [15, 13, 11, 9, 7, 5]);

    static assert(!is(typeof( Iota!(15, 3, 0) ))); // stride = 0 statically
asserts
} // End tests of Iota!()


void main() {}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 06 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085




Static foreach loops have a small disadvantage. This is the original code:

const int sum1 = foo!10() + foo!15() + foo!80();


The same using a static foreach:

int sum2;
foreach (x; TypeTuple!(10, 15, 80))
  sum2 += foo!x();


The small disadvantage is that now x can't be const.
In theory a smarter type system is able to see sum2 too is const.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 01 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085


monarchdodra gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |temtaime gmail.com



*** Issue 10712 has been marked as a duplicate of this issue. ***

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085


monarchdodra gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |monarchdodra gmail.com





 *** Issue 10712 has been marked as a duplicate of this issue. ***


Copy pasting a proposed implementation from 10712. Pretty much the same thing,
but also handles indiscriminate types. It passes the prior tests, as well as
handles the useage with doubles, or chars:

//--------
template Iota(alias h)
{
    alias Iota = IotaImpl!(0, h, 1);
}
template Iota(alias l, alias h)
{
    alias Iota = IotaImpl!(l, h, 1);
}
template Iota(alias l, alias h, alias inc)
{
    alias Iota = IotaImpl!(l, h, inc);
}

template IotaImpl(alias l, alias h, alias inc, T...)
{
    alias E = CommonType!(l, h, inc);
    static if (inc == 0)
        static assert(0, "increment must be non-0");
    else static if (inc > 0 && l >= h)
        alias IotaImpl = T;
    else static if(inc < 0 && l <= h)
        alias IotaImpl = T;
    else
        alias IotaImpl = IotaImpl!(cast(E)(l + inc), h, inc, T, cast(E)l);
}
//--------

//--------
    foreach(idx; Iota!(0, 0))
    write(idx, ' '); // prints 
    writeln();

    foreach(idx; Iota!(0, 10))
    write(idx, ' '); // prints 0, 1, ..., 9
    writeln();

    foreach(idx; Iota!(2, 10))
    write(idx, ' '); // prints 2, 3, ..., 9
    writeln();

    foreach(idx; Iota!(0, -10, -1))
    write(idx, ' '); // prints 0, -1, ..., -9
    writeln();

    foreach_reverse(idx; Iota!(-9, 1))
    write(idx, ' '); // prints 0, -1, ..., -9
    writeln();

    foreach(idx; Iota!(0.5, 10))
    write(idx, ' '); // prints 0.5, 1.5, ..., 9.5
    writeln();

    foreach(idx; Iota!(0, 1, 0.1))
    write(idx, ' '); // prints 0 0.1 ... 0.9
    writeln();

    foreach(idx; Iota!('a', cast(char)('z' + 1), cast(char)1))
    write(idx, ' '); // prints a b ... z
    writeln();
//--------

Maybe it's time to submit this to phobos?

This belongs in typecons?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085




I'm agree with Monarchdodra.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085







 Copy pasting a proposed implementation from 10712. Pretty much the same thing,
 but also handles indiscriminate types. It passes the prior tests, as well as
 handles the useage with doubles, or chars:


Good (despite in my code I avoid using std.range.iota() with floating point
numbers, because to me it seems a bit bug-prone).



 Maybe it's time to submit this to phobos?


I prefer a "static foreach" in the D language, even a very simple one (example:
you can't use a foreach(Iota) at module scope). But in the meantime it's handy
to have a Iota() in Phobos.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085







 Copy pasting a proposed implementation from 10712. Pretty much the same thing,
 but also handles indiscriminate types. It passes the prior tests, as well as
 handles the useage with doubles, or chars:


Just a reminder: elsewhere I asked for an improvement to iota(), to let it
optionally accept a string (like std.random.uniform) that allows to generate
complete intervals of a type or handy closed intervals:

iota!"[]"('a', 'z')
iota!"[]"(cast(ubyte)0, cast(ubyte)255)

Currently I think it's impossible to generate the full range of a type like
ubyes with iota, and it's not handy to generate the complete range of lowercase
char letters, you need to use iota('a', '{'), that currently doesn't work for
other reasons.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085







 

 Copy pasting a proposed implementation from 10712. Pretty much the same thing,
 but also handles indiscriminate types. It passes the prior tests, as well as
 handles the useage with doubles, or chars:


 
 Just a reminder: elsewhere I asked for an improvement to iota(), to let it
 optionally accept a string (like std.random.uniform) that allows to generate
 complete intervals of a type or handy closed intervals:
 
 iota!"[]"('a', 'z')
 iota!"[]"(cast(ubyte)0, cast(ubyte)255)


http://d.puremagic.com/issues/show_bug.cgi?id=10466

I've taken note. I think it is a good idea, but it might be difficult to
implement what with all the overloads.


 Currently I think it's impossible to generate the full range of a type like
 ubyes with iota, and it's not handy to generate the complete range of lowercase
 char letters, you need to use iota('a', '{'), that currently doesn't work for
 other reasons.


http://d.puremagic.com/issues/show_bug.cgi?id=6447
http://d.puremagic.com/issues/show_bug.cgi?id=9447

Fixing the issue of iota and "non built-in integral" is on my "todo" list.

BTW, you could also write it as (provided char is accepted at all):
iota('a', cast(char)('f' + 1))
or
iota!(char,char)('a', 'f'+1);

But in both cases, integral promotion kind of gets in the way of "clean" code
:/

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 26 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085




https://github.com/D-Programming-Language/phobos/pull/1440

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 29 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085




Adapted from two comments by Timon Gehr:


 It's important to keep them separate regardless. static foreach is close 
 to useless if it introduces a new scope for its body.
 
 I.e.:
 
 int main() {
     foreach (_; Seq!int) {
         int x;
     }
     return x; // error
 }
 
 int main() {
     static foreach (_; Seq!int) {
         int x;
     }
     return x; // ok
 }
 
 I think the relationship between foreach and static foreach 
 should essentially mirror that of if and static if.


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 22 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4085




Another comment by Timon Gehr:


 We really need to define a consistent semantics for compile 
 time symbol manipulation though.

 Eg:

 class C{
     int a;
     static foreach(x;__traits(allMembers,C)){
         mixin("int "~__traits(identifier,x)~"b;");
     }
 }

 What is this supposed to do? "class C{ int a,ab; }"? 
 Non-terminating compilation? Error?

 My best guess is that the above code should be illegal,


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 22 2013