www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Conditional purity

reply bearophile <bearophileHUGS lycos.com> writes:
I think that some years from now, in situations where D will be used used in
functional-style programming, the pure attribute for functions will be
important and useful.

In functional-style programming you often use Higher-Order Functions like map,
filter and reduce. So it can be quite positive if the compiler is able to see
they too are pure, because you can perform many optimizations with those HOFs
too. For example the compiler can convert a filter(map()) to a often faster
map(filter()), but only if the mapping/filtering functions given to both map
and filter are pure.

Current D type system is already strong enough allow the creation of a pure
map() HOF. I have a small question in D.learn about literals:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.learn&article_id=20691

But a bigger problem is that I can't see a way to define a conditionally pure
templated function, for example a map() that is pure if the given function
pointer is pure, and is not pure otherwise:


import std.traits: functionAttributes, FunctionAttribute, isCallable;
import std.stdio: writeln;

/// handy, missing in std.traits
template isPure(F) if (isCallable!(F)) {
    enum bool isPure = functionAttributes!(F) & FunctionAttribute.PURE;
}

pure int sqr(int x) { return x * x; }

int tot = 2;
int adder(int x) { return x + tot; } // not pure

pure int[] map1(TF)(TF func, int[] array) {
    int[] result = new int[array.length];
    foreach (i, item; array)
        result[i] = func(item);
    return result;
}

pure auto map2(TF)(TF func, int[] array) {
    int[] result = new int[array.length];
    foreach (i, item; array)
        result[i] = func(item);
    return result;
}

auto map3(TF)(TF func, int[] array) {
    int[] result = new int[array.length];
    foreach (i, item; array)
        result[i] = func(item);
    return result;
}

void main() {
    int[] arr1 = [1, 2, 3, 4, 5];
    writeln(arr1);

    int[] arr2 = map1(&sqr, arr1);
    writeln(arr2);

    writeln(isPure!(typeof(&map1!(typeof(&sqr))))); // true
    writeln(isPure!(typeof(&map2!(typeof(&sqr))))); // false

    int[] arr3 = map2(&adder, arr1);
    writeln(arr3);
    writeln(isPure!(typeof(&map3!(typeof(&sqr))))); // false
}


I think using 'auto' isn't a solution.
(map2() also shows that when there is an 'auto' the 'pure' gets ignored. I
don't know if this is a bug for Bugzilla.)

This problem looks a bit like the 'auto ref' attribute :-) If you can't see a
solution then maybe a more general solution can be considered.

Bye,
bearophile
Jul 24 2010
next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:

 But a bigger problem is that I can't see a way to define a conditionally  
 pure templated function, for example a map() that is pure if the given  
 function pointer is pure, and is not pure otherwise:

This is fairly simple currently: template map( alias fn ) { // blah blah blah, whatever is necessary here static if ( isPure!fn ) { pure map( Range )( Range r ) { ... } } else { auto map( Range )( Range r ) { ... } } } Of course, this leads to code duplication, which is unwanted. In cases like this, I long for some features of the C preprocessor, which would be able to insert any kind of code wherever it wants. This feature request, and Steve's problems with final (in std.pattern..mixin temptes..std.concurrency), makes me think there should be some way to specify all (or at least most) such conditionally. There seems to be a real need for it. -- Simen
Jul 25 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Simen kjaeraas:
 This is fairly simple currently:
 
 template map( alias fn ) { // blah blah blah, whatever is necessary here
      static if ( isPure!fn ) {
          pure map( Range )( Range r ) { ... }
      } else {
          auto map( Range )( Range r ) { ... }
      }
 }

Do you mean code like this (this doesn't work yet)? import std.traits: functionAttributes, FunctionAttribute, isCallable; import std.stdio: writeln; pure int sqr(int x) { return x * x; } int tot = 2; int adder(int x) { return x + tot; } // not pure template map(alias fn) { static if (isPure!fn) { pure int[] map(int[] array) { int[] result = new int[array.length]; foreach (i, item; array) result[i] = func(item); return result; } } else { int[] map(int[] array) { int[] result = new int[array.length]; foreach (i, item; array) result[i] = func(item); return result; } } } template isPure(F) if (isCallable!(F)) { enum bool isPure = functionAttributes!(F) & FunctionAttribute.PURE; } void main() { int[] arr1 = [1, 2, 3, 4, 5]; writeln(arr1); int[] arr2 = map!(&sqr)(arr1); writeln(arr2); int[] arr3 = map!(&adder)(arr1); writeln(arr3); //writeln(isPure!(typeof(&map!(typeof(&sqr))))); //writeln(isPure!(typeof(&map!(typeof(&adder))))); } I suggest all people in all D newsgroups, to write code that runs, not uncompilable snippets. All errors in the last Walter's talk can be avoided in few minutes running the code. In Python newsgroups 90% of the code snippets are run before they are shown to people.
 Of course, this leads to code duplication, which is unwanted.

You can probably remove the duplication using a mixin but this makes things worse :-)
 In cases
 like this, I long for some features of the C preprocessor, which would
 be able to insert any kind of code wherever it wants.

It's much better to look for more clean solutions.
 This feature request, and Steve's problems with final (in
 std.pattern..mixin temptes..std.concurrency), makes me think there
 should be some way to specify all (or at least most) such conditionally.
 There seems to be a real need for it.

A silly idea to add or not add an attribute: import std.traits: IF = Select; IF!(isPure!TF, pure, nothing) int[] map(TF)(TF func, int[] array) {...} Bye, bearophile
Jul 25 2010
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:

 Simen kjaeraas:
 This is fairly simple currently:


 Do you mean code like this (this doesn't work yet)?

Yeah.
 I suggest all people in all D newsgroups, to write code that runs, not  
 uncompilable snippets. All errors in the last Walter's talk can be  
 avoided in few minutes running the code. In Python newsgroups 90% of the  
 code snippets are run before they are shown to people.

Of course. But not always does time allow us such excesses. :p
 In cases
 like this, I long for some features of the C preprocessor, which would
 be able to insert any kind of code wherever it wants.

It's much better to look for more clean solutions.

That was kinda my point. :p
 This feature request, and Steve's problems with final (in
 std.pattern..mixin temptes..std.concurrency), makes me think there
 should be some way to specify all (or at least most) such conditionally.
 There seems to be a real need for it.

A silly idea to add or not add an attribute: import std.traits: IF = Select; IF!(isPure!TF, pure, nothing) int[] map(TF)(TF func, int[] array) {...}

I'd be fine with something like that. Or (Inspiration taken from template constraints): ( pure if ( isPure!TF ) ) ( nothrow if ( isNothrow!TF ) ) int[] map(TF)(TF func, int[] array) {...} -- Simen
Jul 25 2010