Conditional purity

bearophile bearophileHUGS at lycos.com
Sat Jul 24 16:48:04 PDT 2010


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


More information about the Digitalmars-d mailing list