View mode: basic / threaded / horizontal-split · Log in · Help
July 24, 2010
Conditional purity
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
July 25, 2010
Re: Conditional purity
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
July 25, 2010
Re: Conditional purity
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
July 25, 2010
Re: Conditional purity
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
4 days ago
Re: Conditional purity
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_
4 days ago
Re: Conditional purity
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...
Top | Discussion index | About this forum | D home