www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Pure higher order functions

reply bearophile <bearophileHUGS lycos.com> writes:
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?

Bye,
bearophile
Jul 06 2011
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Jul 06 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:
 

 I believe that the problem here is essentially what's being argued over
 in the dmd-beta list right now.


In D a HOF is implemented with a struct or a class. So, what's a pure
struct/class, generally?

Bye,
bearophile
Jul 06 2011
next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On 2011-07-06 16:19, bearophile wrote:

 Jonathan M Davis:

 I believe that the problem here is essentially what's being argued over
 in the dmd-beta list right now.


 
 In D a HOF is implemented with a struct or a class. So, what's a pure
 struct/class, generally?


I don't think that it makes any sense to talk about a pure struct or class. 
Functions are pure, not types. However, given that applying a modifier to a 
type seems to generally end up applying it to all of the type's functions, 
then marking a type as pure should mark all of its functions as pure. That's 
not what I was talking about though. I was talking about how weakly pure was 
essentially stripped out of the language with recent compiler changes. Whether 
marking a type as pure does anything is another issue entirely.

- Jonathan M Davis
Jul 06 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


I don't think that it makes any sense to talk about a pure struct or class.
Functions are pure, not types.<


In my opinion, if D wants to solve the issue of pure HOFs, then it has to
decide (or invent) what a pure struct (instance, if you want) is.

Bye,
bearophile
Jul 06 2011
next sibling parent KennyTM~ <kennytm gmail.com> writes:
On Jul 7, 11 10:02, bearophile wrote:

 Jonathan M Davis:


 I don't think that it makes any sense to talk about a pure struct or class.
Functions are pure, not types.<


 In my opinion, if D wants to solve the issue of pure HOFs, then it has to
decide (or invent) what a pure struct (instance, if you want) is.

 Bye,
 bearophile


A method 'S.f(T) constness' is pure iff 'f(ref constness(S) this, T)' is 
pure. No pure struct needed.
Jul 06 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
With the latest beta update this compiles:


 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 .. $];
}

struct Map(alias fun, R) {
    R _input;

    this(R input) nothrow pure {
        _input = input;
    }

     property bool empty() nothrow const pure {
        return _input.empty;
    }

     property auto ref front() nothrow const pure {
        return fun(_input.front);
    }

    void popFront() nothrow pure {
        _input.popFront();
    }
}

template map(alias fun) {
    auto pure 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);
}


But I have had to write, this I don't know why:
auto pure map(R)(R range) {

And despite Map is a template, its methods aren't pure, so I have had to write
them with pure:
 property bool empty() nothrow const pure {

So I think currently map() can't be pure.
I think we need the notion of pure structs/classes (instances).

Bye,
bearophile
Jul 07 2011
next sibling parent reply KennyTM~ <kennytm gmail.com> writes:
On Jul 7, 11 19:34, bearophile wrote:

 With the latest beta update this compiles:


  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 .. $];
 }

 struct Map(alias fun, R) {
      R _input;

      this(R input) nothrow pure {
          _input = input;
      }

       property bool empty() nothrow const pure {
          return _input.empty;
      }

       property auto ref front() nothrow const pure {
          return fun(_input.front);
      }

      void popFront() nothrow pure {
          _input.popFront();
      }
 }

 template map(alias fun) {
      auto pure 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);
 }


 But I have had to write, this I don't know why:
 auto pure map(R)(R range) {

 And despite Map is a template, its methods aren't pure, so I have had to write
them with pure:
  property bool empty() nothrow const pure {

 So I think currently map() can't be pure.
 I think we need the notion of pure structs/classes (instances).

 Bye,
 bearophile


No, I think it's a bug in pure-inference.

pure int h() {
     return 1;
}
int f(alias g)() {
     return g();
}
pure int i() {
     return f!h();  // pure function 'i' cannot call impure function 'f'
}
Jul 07 2011
parent reply KennyTM~ <kennytm gmail.com> writes:
On Jul 8, 11 00:43, KennyTM~ wrote:

 No, I think it's a bug in pure-inference.

 pure int h() {
      return 1;
 }
 int f(alias g)() {
      return g();
 }
 pure int i() {
      return f!h();  // pure function 'i' cannot call impure function 'f'
 }


http://d.puremagic.com/issues/show_bug.cgi?id=6265
Jul 07 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
KennyTM~:


 On Jul 8, 11 00:43, KennyTM~ wrote:

 No, I think it's a bug in pure-inference.

 pure int h() {
      return 1;
 }
 int f(alias g)() {
      return g();
 }
 pure int i() {
      return f!h();  // pure function 'i' cannot call impure function 'f'
 }


 
 http://d.puremagic.com/issues/show_bug.cgi?id=6265


I was probably wrong, as usual. Thank you for seeing the real problem and for
the bug report :-)
Maybe this is worth fixing before DMD 2.054 goes out of beta, I am not sure.

Bye,
bearophile
Jul 07 2011
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On 2011-07-07 15:19, bearophile wrote:

 KennyTM~:

 On Jul 8, 11 00:43, KennyTM~ wrote:

 No, I think it's a bug in pure-inference.
 
 pure int h() {
 
 return 1;
 
 }
 int f(alias g)() {
 
 return g();
 
 }
 pure int i() {
 
 return f!h(); // pure function 'i' cannot call impure function
 'f'
 
 }


 
 http://d.puremagic.com/issues/show_bug.cgi?id=6265


 
 I was probably wrong, as usual. Thank you for seeing the real problem and
 for the bug report :-) Maybe this is worth fixing before DMD 2.054 goes
 out of beta, I am not sure.


It certainly needs fixing, but I don't know how high a priority it's going to 
be to fix issues related to purity inference with 2.054 given that it's a new 
feature and so bugs related to it aren't likely to be regressions. If it 
doesn't get fixed for 2.054 though, it'll probably be fixed for 2.055. 
Regardless, the overall situation with purity is improving.

- Jonathan M Davis
Jul 07 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 Regardless, the overall situation with purity is improving.


I agree. Someday I hope to see another little improvement in the D type system,
to allow code like this to compile without the need of a cast of s2 to string
at the end:

string foo(in string s) pure nothrow { // strongly pure
    char[] s2 = s.dup; // dup will become nothrow
    s2[0] = 'A';
    return s2;
}

(alternative design of this feature: this foo returns a char[] but then you are
allowed to assign this result to a string).

Seeing the recent large amount of pull requests I am seeing, is someone willing
to implement this type system feature?

Bye,
bearophile
Jul 08 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
 Seeing the recent large amount of pull requests I am seeing, is someone
willing to implement this type system feature?


yebblies delivers, quickly too :-)
http://d.puremagic.com/issues/show_bug.cgi?id=5081
https://github.com/D-Programming-Language/dmd/pull/218

At this rhythm of improvements D/dmd will become better in few months :-)

Bye and thank you,
bearophile
Jul 09 2011
parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:iv9grs$286j$1 digitalmars.com...

 Seeing the recent large amount of pull requests I am seeing, is someone 
 willing to implement this type system feature?


 yebblies delivers, quickly too :-)
 http://d.puremagic.com/issues/show_bug.cgi?id=5081
 https://github.com/D-Programming-Language/dmd/pull/218


Only for strongly pure functions - not const pure at this point.  Still, it 
should make construction of immutable structures without casting a lot 
easier.
Jul 09 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Daniel Murphy:


 Only for strongly pure functions - not const pure at this point.


I see, OK.



 Still, it should make construction of immutable structures without casting a
lot easier.


I presume you mean something like this ("function" is currently required if you
want to add "pure" too):


void main() {
    int n = 5; // mutable;

    immutable data = function(in int m) pure {
        class Foo {}
        auto array = new Foo[m];
        foreach (ref item; array)
            item = new Foo;
        return array;
    }(n);

    // use data here
}

--------------

If you have some more energy, Walter has (I think) accepted two of my
enhancement requests, but they don't have a complete patch yet (both have low
priority):

3827 automatic joining of adjacent strings is bad [partial patch present]
5409 Disallow (!x & y)

Bye,
bearophile
Jul 09 2011
parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:iva7iv$b6v$1 digitalmars.com...

 Still, it should make construction of immutable structures without 
 casting a lot easier.


 I presume you mean something like this ("function" is currently required 
 if you want to add "pure" too):


Or use a nested function.  Either way, no casting or assumeUnique required.
function shouldn't be required once 
http://d.puremagic.com/issues/show_bug.cgi?id=3235 is fixed.


 3827 automatic joining of adjacent strings is bad [partial patch present]


The patch for this seems solid, I might make a pull for it after the 
release.


 5409 Disallow (!x & y)


This seems like it would require modifying the parser, which I'm not 
particularly good at yet.  Maybe later.
Jul 09 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Daniel Murphy:


 function shouldn't be required once 
 http://d.puremagic.com/issues/show_bug.cgi?id=3235 is fixed.


OK.



 3827 automatic joining of adjacent strings is bad [partial patch present]


 The patch for this seems solid, I might make a pull for it after the 
 release.


Is a good enough error message generated by the patch?
Do you want the automatic joining (without ~) to work if the -d switch is used?
(I think this is not needed).



 This seems like it would require modifying the parser, which I'm not 
 particularly good at yet.  Maybe later. 


OK.

Thank you for your work and your answers :-)
Bye,
bearophile
Jul 10 2011
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On 2011-07-07 04:34, bearophile wrote:

 With the latest beta update this compiles:
 
 
  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 .. $];
 }
 
 struct Map(alias fun, R) {
 R _input;
 
 this(R input) nothrow pure {
 _input = input;
 }
 
  property bool empty() nothrow const pure {
 return _input.empty;
 }
 
  property auto ref front() nothrow const pure {
 return fun(_input.front);
 }
 
 void popFront() nothrow pure {
 _input.popFront();
 }
 }
 
 template map(alias fun) {
 auto pure 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);
 }
 
 
 But I have had to write, this I don't know why:
 auto pure map(R)(R range) {
 
 And despite Map is a template, its methods aren't pure, so I have had to
 write them with pure:  property bool empty() nothrow const pure {
 
 So I think currently map() can't be pure.
 I think we need the notion of pure structs/classes (instances).


And what would that even mean? Purity for types makes no sense. It only makes 
sense for functions. What it sounds like is that the purity inference isn't 
working when it's the type which is templated instead of the function. If 
that's the case, then the purity inference needs to be improved. But it's 
brand new, so it's no surprise if it doesn't work entirely correctly.

- Jonathan M Davis
Jul 07 2011