www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Nesting in pure functions

reply bearophile <bearophileHUGS lycos.com> writes:
This post was originally meant for digitalmars.D.learn, but maybe it can
interest more people here.

Now that the D1/D2 zips have a better internal structure and don't require DMC
anymore I am more free to use D2 more, so I have tried to understand how the
optimization of pure functions works.

So I have written this toy program that computes:
((x*x)+(x*x)) + ((x*x)+(x*x))


import std.c.stdio: printf;
import std.conv: toInt;

pure int double_sqr(int x) {
    int y, z;
    void do_sqr() { y *= y; }
    y = x;
    do_sqr();
    z += y;
    y = x;
    do_sqr();
    z += y;
    return z;
}

void main(string[] args) {
    int x = args.length == 2 ? toInt(args[1]) : 10;
    int y = double_sqr(x) + double_sqr(x);
    printf("4 * x * x = %d\n", y);
}

double_sqr() is a pure function. do_sqr() isn't a pure function, but it has no
side effects outside double_sqr(), so double_sqr() is globally pure still. But
the compiler (dmd v2.027) doesn't accept it (notice the strange blank line in
the middle):

pure_test3.d(...): Error: pure function 'double_sqr' cannot call impure
function 'do_sqr'

pure_test3.d(...): Error: pure function 'double_sqr' cannot call impure
function 'do_sqr'

So I have tried to simplify the life of the compiler, changing do_sqr() to
sqr() that is something simpler and pure:

pure int double_sqr(int x) {
    int sqr(int y) { return y * y; }
    return sqr(x) + sqr(x);
}

But that doesn't work still:

pure_test3.d(...): Error: pure function 'double_sqr' cannot call impure
function 'sqr'

So I've added a pure statement to sqr() too, to state its status:

pure int double_sqr(int x) {
    pure int sqr(int y) { return y * y; }
    return sqr(x) + sqr(x);
}

But it's not acceptable still:

pure_test3.d(...): found 'pure' instead of statement
pure_test3.d(...): Declaration expected, not 'return'
pure_test3.d(...): unrecognized declaration

The good thing of pure functions in D is that they are supposed to allow you to
do impure things inside them, as long as you keep the whole function pure. But
it seems nested functions can't be used yet inside pure functions. Is this
something that can be improved/changed in future?

Bye,
bearophile
Apr 06 2009
parent reply Don <nospam nospam.com> writes:
bearophile wrote:
 This post was originally meant for digitalmars.D.learn, but maybe it can
interest more people here.
 
 Now that the D1/D2 zips have a better internal structure and don't require DMC
anymore I am more free to use D2 more, so I have tried to understand how the
optimization of pure functions works.
 
 So I have written this toy program that computes:
 ((x*x)+(x*x)) + ((x*x)+(x*x))
 
 
 import std.c.stdio: printf;
 import std.conv: toInt;
 
 pure int double_sqr(int x) {
     int y, z;
     void do_sqr() { y *= y; }
     y = x;
     do_sqr();
     z += y;
     y = x;
     do_sqr();
     z += y;
     return z;
 }
 
 void main(string[] args) {
     int x = args.length == 2 ? toInt(args[1]) : 10;
     int y = double_sqr(x) + double_sqr(x);
     printf("4 * x * x = %d\n", y);
 }
 

 double_sqr() is a pure function. do_sqr() isn't a pure function, but it has no
side effects outside double_sqr(), so double_sqr() is globally pure still. But
the compiler (dmd v2.027) doesn't accept it (notice the strange blank line in
the middle):

There's some compiler bugs. Try: void do_sqr() pure { y *= y; } and it compiles, but generates wrong code. pure void do_sqr() doesn't compile. Nothrow behaves the same. Compare with bugzilla 2694. But this one works: pure int double_sqr(int x) { int z; int do_sqr(int y) pure { return y*y; } z = do_sqr(x); z += do_sqr(x); return z; }
Apr 06 2009
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Don:
 But this one works:
 
 pure int double_sqr(int x) {
      int z;
      int do_sqr(int y) pure { return y*y; }
      z = do_sqr(x);
      z += do_sqr(x);
      return z;
 }

Right, thank you. But why the pure is after the argument list? I didn't even know that syntax is allowed. I have then compiled: import std.c.stdio: printf; import std.conv: toInt; pure int double_sqr(int x) { int sqr(int y) pure { return y * y; } return sqr(x) + sqr(x); } void main(string[] args) { int x = args.length == 2 ? toInt(args[1]) : 10; int y = double_sqr(x) + double_sqr(x); printf("4 * x * x = %d\n", y); } The asm generated by D2 with no inlining: sqr: mov EAX,4[ESP] imul EAX,EAX ret 4 double_sqr: L0: push EAX push EAX xor EAX,EAX call near ptr sqr add EAX,EAX pop ECX ret main: L0: push EAX cmp dword ptr 8[ESP],2 jne L1D mov EDX,0Ch[ESP] mov EAX,8[ESP] push dword ptr 0Ch[EDX] push dword ptr 8[EDX] call near ptr toInt jmp short L22 L1D: mov EAX,0Ah L22: call near ptr double_sqr add EAX,EAX mov ECX,offset FLAT:_DATA push EAX push ECX call near ptr printf So pure is correctly optimized in both places. I don't know why sqr is written like this: sqr: imul EAX,EAX ret Bye, bearophile
Apr 06 2009
parent bearophile <bearophileHUGS lycos.com> writes:
bearophile:
 I don't know why sqr is written like this:

Sorry, I meant:
I don't know why sqr isn't written like this:<

-------------------- This is the same compiled with -inline too, as you can see double_sqr() isn't being inlined, despite containing just an imul and an add: sqr: mov EAX,4[ESP] imul EAX,EAX ret 4 double_sqr: imul EAX,EAX add EAX,EAX ret main: L0: push EAX cmp dword ptr 8[ESP],2 jne L1D mov EDX,0Ch[ESP] mov EAX,8[ESP] push dword ptr 0Ch[EDX] push dword ptr 8[EDX] call near ptr toInt jmp short L22 L1D: mov EAX,0Ah L22: call near ptr double_sqr add EAX,EAX mov ECX,offset FLAT:_DATA push EAX push ECX call near ptr printf ------------- Regarding the inlining in D, it's supposed to be automatic, but often the programmer knows better. For a recent example of mine take a look at the "mastermind_breaking.d" program inside this zip: http://www.fantascienza.net/leonardo/js/mastermind_break.zip I have had to put the function code inside a string mixin to force a manual inlining and improve the performance of the program. Bye, bearophile
Apr 06 2009
prev sibling parent reply Don <nospam nospam.com> writes:
Don wrote:
 bearophile wrote:
 This post was originally meant for digitalmars.D.learn, but maybe it 
 can interest more people here.

 Now that the D1/D2 zips have a better internal structure and don't 
 require DMC anymore I am more free to use D2 more, so I have tried to 
 understand how the optimization of pure functions works.

 So I have written this toy program that computes:
 ((x*x)+(x*x)) + ((x*x)+(x*x))


 import std.c.stdio: printf;
 import std.conv: toInt;

 pure int double_sqr(int x) {
     int y, z;
     void do_sqr() { y *= y; }
     y = x;
     do_sqr();
     z += y;
     y = x;
     do_sqr();
     z += y;
     return z;
 }

 void main(string[] args) {
     int x = args.length == 2 ? toInt(args[1]) : 10;
     int y = double_sqr(x) + double_sqr(x);
     printf("4 * x * x = %d\n", y);
 }

 double_sqr() is a pure function. do_sqr() isn't a pure function, but 
 it has no side effects outside double_sqr(), so double_sqr() is 
 globally pure still. But the compiler (dmd v2.027) doesn't accept it 
 (notice the strange blank line in the middle):

There's some compiler bugs. Try: void do_sqr() pure { y *= y; } and it compiles, but generates wrong code. pure void do_sqr() doesn't compile. Nothrow behaves the same. Compare with bugzilla 2694. But this one works: pure int double_sqr(int x) { int z; int do_sqr(int y) pure { return y*y; } z = do_sqr(x); z += do_sqr(x); return z; }

a bug. Patch: In expression.c, around line 1100, you can disable the purity check if it's a nested function: void Expression::checkPurity(Scope *sc, FuncDeclaration *f) { if (sc->func && sc->func->isPure() && !sc->intypeof && (!f->isNested() && !f->isPure())) ----- But, this still isn't enough, because it doesn't check the nested functions for purity. Rather than checking if the function is pure, FuncDeclaration needs 'ultimatelyPure' and 'ultimatelyNothrow' members, which are assigned when the declaration is encountered. Almost all purity checks need to be made against the 'ultimatelyPure' member. (But things like purity of delegates would be made from the 'pure' member rather than the 'ultimately pure' member).
Apr 06 2009
parent reply Don <nospam nospam.com> writes:
Don wrote:
 Don wrote:
 bearophile wrote:
 This post was originally meant for digitalmars.D.learn, but maybe it 
 can interest more people here.

 Now that the D1/D2 zips have a better internal structure and don't 
 require DMC anymore I am more free to use D2 more, so I have tried to 
 understand how the optimization of pure functions works.

 So I have written this toy program that computes:
 ((x*x)+(x*x)) + ((x*x)+(x*x))


 import std.c.stdio: printf;
 import std.conv: toInt;

 pure int double_sqr(int x) {
     int y, z;
     void do_sqr() { y *= y; }
     y = x;
     do_sqr();
     z += y;
     y = x;
     do_sqr();
     z += y;
     return z;
 }

 void main(string[] args) {
     int x = args.length == 2 ? toInt(args[1]) : 10;
     int y = double_sqr(x) + double_sqr(x);
     printf("4 * x * x = %d\n", y);
 }

 double_sqr() is a pure function. do_sqr() isn't a pure function, but 
 it has no side effects outside double_sqr(), so double_sqr() is 
 globally pure still. But the compiler (dmd v2.027) doesn't accept it 
 (notice the strange blank line in the middle):

There's some compiler bugs. Try: void do_sqr() pure { y *= y; } and it compiles, but generates wrong code. pure void do_sqr() doesn't compile. Nothrow behaves the same. Compare with bugzilla 2694. But this one works: pure int double_sqr(int x) { int z; int do_sqr(int y) pure { return y*y; } z = do_sqr(x); z += do_sqr(x); return z; }

a bug. Patch: In expression.c, around line 1100, you can disable the purity check if it's a nested function: void Expression::checkPurity(Scope *sc, FuncDeclaration *f) { if (sc->func && sc->func->isPure() && !sc->intypeof && (!f->isNested() && !f->isPure())) ----- But, this still isn't enough, because it doesn't check the nested functions for purity. Rather than checking if the function is pure, FuncDeclaration needs 'ultimatelyPure' and 'ultimatelyNothrow' members, which are assigned when the declaration is encountered. Almost all purity checks need to be made against the 'ultimatelyPure' member. (But things like purity of delegates would be made from the 'pure' member rather than the 'ultimately pure' member).

Actually, it's much easier than I thought. Here's a patch that prevents inner functions from calling impure external ones, and accessing static variables. (sorry that this isn't a proper patch, I've hacked my DMD so much by now, the line numbers would be all wrong... <g>) around line 1100: void Expression::checkPurity(Scope *sc, FuncDeclaration *f) { if (sc->func) { FuncDeclaration *outerfunc=sc->func; while (outerfunc->toParent2() && outerfunc->toParent2()->isFuncDeclaration()) outerfunc = outerfunc->toParent2()->isFuncDeclaration(); if (outerfunc->isPure() && !sc->intypeof && (!f->isNested() && !f->isPure())) error("pure function '%s' cannot call impure function '%s'\n", sc->func->toChars(), f->toChars()); } } and around line 4000, change this code: #if DMDV2 if (sc->func && sc->func->isPure() && !sc->intypeof) { if (v->isDataseg() && !v->isInvariant()) error("pure function '%s' cannot access mutable static data '%s'", sc->func->toChars(), v->toChars()); } #endif into: #if DMDV2 if (sc->func) { FuncDeclaration *outerfunc=sc->func; while (outerfunc->toParent2() && outerfunc->toParent2()->isFuncDeclaration()) { outerfunc = outerfunc->toParent2()->isFuncDeclaration(); } if (outerfunc->isPure() && !sc->intypeof && v->isDataseg() && !v->isInvariant()) error("pure function '%s' cannot access mutable static data '%s'", sc->func->toChars(), v->toChars()); } #endif --------------------
Apr 06 2009
parent reply bearophile <bearophileHUGS lycos.com> writes:
Don:
 (sorry that this isn't a proper patch, I've hacked my DMD so 
 much by now, the line numbers would be all wrong... <g>)

Ah lol :-) What have you done to your poor DMD? Are such changes good/interesting enough for Walter to be interested in them? Bye, bearophile
Apr 06 2009
parent Don <nospam nospam.com> writes:
bearophile wrote:
 Don:
 (sorry that this isn't a proper patch, I've hacked my DMD so 
 much by now, the line numbers would be all wrong... <g>)

Ah lol :-) What have you done to your poor DMD? Are such changes good/interesting enough for Walter to be interested in them?

They're fixes for segfaults. All are in bugzilla. I've created this as 2804, and made a proper patch for it. (Having access to the compiler backend is so cool! Thanks, Walter!)
 
 Bye,
 bearophile

Apr 06 2009