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
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 reply 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
parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:


 Simen kjaeraas:

 This is fairly simple currently:




[snip]

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


[snip]

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
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Sunday, 25 July 2010 at 14:10:10 UTC, Simen kjaeraas wrote:

Update: Members of FunctionAttribute have been renamed from 
uppercase to lowercase and when needed an underscore has been 
added to the enumerators that conflict with keywords such as: 
PURE has been renamed to pure_
Aug 29 2014
prev sibling parent "Andrew Godfrey" <X y.com> writes:
On Sunday, 25 July 2010 at 14:10:10 UTC, Simen kjaeraas wrote:

 bearophile <bearophileHUGS lycos.com> wrote:


 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


Think of the time it costs us all when we incorporate an idea 
that doesn't work into our thinking.
Bearophile is right, I've been feeling this too.

Even worse, the documentation has code that doesn't compile.
This surprised me because D is so strong on unit tests and doc 
generation...
Aug 29 2014