Pure higher order functions

Jonathan M Davis jmdavisProg at gmx.com
Wed Jul 6 15:52:02 PDT 2011


On 2011-07-06 15:42, bearophile wrote:
> I think D eventually needs to allow the creation of pure higher order
> functions, like map, filter, amap (that means array(map(...))).
> 
> 
> DMD 2.054beta improves the situation with the automatic inference for pure
> and nothrow.
> 
> (By the way, the changelog says "Add warning about calling pure nothrow
> functions and ignoring the result", but this was reverted).
> 
> Currently this code doesn't compile, but I expect it to eventually compile
> if D wants to be a bit functional:
> 
> 
> import std.range, std.algorithm;
> 
> int sqr(int x) pure nothrow { return x * x; }
> 
> pure int foo(int n) {
> int total;
> foreach (x; map!sqr([1, 2, 3, 4]))
> total += 1;
> return total;
> }
> 
> void main() {
> int x = foo(10);
> }
> 
> 
> It gives the errors:
> 
> test.d(8): Error: pure function 'foo' cannot call impure function 'map'
> test.d(8): Error: pure function 'foo' cannot call impure function 'empty'
> test.d(8): Error: pure function 'foo' cannot call impure function
> 'popFront' test.d(8): Error: pure function 'foo' cannot call impure
> function 'front'
> 
> (Note how the error messages don't tell me in what module those 'map',
> 'empty', 'popFront' and 'front' are. I think this is worth an enhancement
> request.)
> 
> To see the situation better I have created a simpler version without Phobos
> imports (no @safe to keep things simpler):
> 
> 
> 
> @property bool empty(T)(in T[] a) pure nothrow {
> return !a.length;
> }
> 
> @property ref T front(T)(T[] a) pure nothrow {
> assert(a.length);
> return a[0];
> }
> 
> void popFront(A)(ref A a) pure nothrow {
> assert(a.length);
> a = a[1 .. $];
> }
> 
> pure struct Map(alias fun, R) {
> R _input;
> 
> this(R input) nothrow {
> _input = input;
> }
> 
> @property bool empty() nothrow const {
> return _input.empty;
> }
> 
> @property auto ref front() nothrow const {
> return fun(_input.front);
> }
> 
> void popFront() nothrow {
> _input.popFront();
> }
> }
> 
> template map(alias fun) {
> auto map(R)(R range) {
> return Map!(fun, R)(range);
> }
> }
> 
> int sqr(int x) pure nothrow { return x * x; }
> 
> pure nothrow int foo(int n) {
> int total;
> foreach (x; map!(sqr)([1, 2, 3, 4]))
> total += x;
> return total;
> }
> 
> void main() {
> assert(foo(10) == 30);
> }
> 
> 
> "pure struct" does nothing, this is bad.
> 
> If I remove the "pure" from foo, it compiles and works, even if I compile
> with -property.
> 
> If I add a "pure" to Map.empty it doesn't compile, with the error:
> test.d(23): Error: pure nested function 'empty' cannot access mutable data
> '_input'
> 
> How do I create a pure higher order function?

I believe that the problem here is essentially what's being argued over in the 
dmd-beta list right now. Walter made some changes recently which pretty much 
removed weak purity. And until that issue is resolved, member functions can't 
be pure, or if they can be, it's only under very limited circumstances. 
Hopefully the situation gets fixed before the release of dmd 2.054, but that 
depends on what Walter does. Certainly, as it stands, 2.054 is going to break 
a lot code which uses pure.

- Jonathan M Davis


More information about the Digitalmars-d mailing list