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;
 }


In fact, the fact that it accepts 'pure' on nested functions is probably 
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;
 }


 In fact, the fact that it accepts 'pure' on nested functions is probably 
 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