<div dir="ltr">I think this is a good discovery. Currently a pure function can have lazy parameters and it is treated as a weakly pure function.<div><br></div><div>pure int foo(lazy int x) { return x; } // OK</div><div><br>
</div><div>We can think the lazy parameter is a limited case of scope delegate parameter.</div><div><br></div><div>And more, I discovered that the purity may be stronger depends on the given delegate purity.</div><div><br>
</div><div><div>void func(scope void delegate(int) dg) pure;</div></div><div><br></div><div>void main() {</div><div> int num;</div><div><br></div><div> // the function call has weak purity<br></div><div> func((x){ num = x;});</div>
<div><br></div><div> // the function call has strong purity<br></div><div> func((x){ ; });</div><div>}</div><div><br></div><div>Kenji Hara</div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">
2013/11/1 H. S. Teoh <span dir="ltr"><<a href="mailto:hsteoh@quickfur.ath.cx" target="_blank">hsteoh@quickfur.ath.cx</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
[I actually came up with this idea last week, but decided to postpone<br>
bringing it up until all the furor about Andrei's new allocator design<br>
has settled a little. ;-)]<br>
<br>
One of the neatest things about purity in D is that traditionally impure<br>
operations like mutation and assignment can be allowed inside a pure<br>
function, as long as the effect is invisible to the outside world. This,<br>
of course, describes strong purity. Weak purity takes it one step<br>
further, by allowing mutation of outside state via references to mutable<br>
data passed in as function arguments.<br>
<br>
I'd like to propose extending the scope of weak purity one step further:<br>
allow weakly-pure functions to call (not necessarily pure) delegates<br>
passed as a parameter. That is, the following code should work:<br>
<br>
// N.B. This is a (weakly) pure function.<br>
void func(scope void delegate(int) dg) pure<br>
{<br>
// N.B. This calls an *impure* delegate.<br>
dg(1);<br>
}<br>
<br>
Before you break out the pitchforks, please allow me to rationalize this<br>
situation.<br>
<br>
The above code is essentially equivalent to:<br>
<br>
void func(void *context, scope void function(void*,int) dg) pure<br>
{<br>
dg(context, 1);<br>
}<br>
<br>
That is to say, passing in a delegate is essentially equivalent to<br>
passing in a mutable reference to some outside state (the delegate's<br>
context), and a pointer to a function that possibly mutates the outside<br>
world through that context pointer. In a sense, this is not that much<br>
different from a weakly pure function that directly modifies the outside<br>
world via the context pointer.<br>
<br>
But, I hear you cry, if func calls an *impure function* via a function<br>
pointer, doesn't that already violate purity??!<br>
<br>
Well, it certainly violates *strong* purity, no question about that. But<br>
consider this code:<br>
<br>
int stronglyPure(int x) pure<br>
{<br>
int[] scratchpad;<br>
scratchpad.length = 2;<br>
<br>
// This is an impure delegate because it closes over<br>
// scratchpad.<br>
auto dg = (int x) { scratchpad[x]++; };<br>
<br>
// Should this work?<br>
func(dg);<br>
<br>
return scratchpad[1];<br>
}<br>
<br>
Think about it. What func does via dg can only ever affect a variable<br>
local to stronglyPure(). It's actually impossible for stronglyPure() to<br>
construct a delegate that modifies a global variable, because the<br>
compiler will complain that referencing a global is not allowed inside a<br>
pure function (verified on git HEAD). Any delegate that stronglyPure()<br>
can construct, can only ever affect its local state. The only way you<br>
could sneak an impure delegate into func() is if stronglyPure() itself<br>
takes an impure delegate as parameter -- but if it does so, then it is<br>
no longer strongly pure.<br>
<br>
IOW, if stronglyPure() is truly strongly pure, then it is actually<br>
impossible for the call to func() to have any effect outside of<br>
stronglyPure()'s local scope, no matter what kind of delegate<br>
stronglyPure() passes to func(). So such a call should be permitted!<br>
<br>
Now let's consider the case where we pass a delegate to func() that<br>
*does* modify global state:<br>
<br>
int global_state;<br>
void main() {<br>
func((int x) { global_state = x; });<br>
}<br>
<br>
In this case, func being marked pure doesn't really cause any issues:<br>
main() itself is already impure because it is constructing a delegate<br>
that closes over a global variable, so the fact that the actual change<br>
comes from calling func no longer matters. It's always OK for impure<br>
code to call pure code, after all. It's no different from this:<br>
<br>
void weaklyPure(int* x) pure {<br>
*x = 1; // OK<br>
}<br>
<br>
int global_state;<br>
void main() {<br>
weaklyPure(&global_state);<br>
}<br>
<br>
That is to say, as long as the code that calls func() is marked pure,<br>
then the behaviour of func() is guaranteed never to affect anything<br>
outside the local scope of the caller (and whatever the caller can reach<br>
via mutable reference parameters). That is, it is (at least) weakly<br>
pure. If the caller is strongly pure (no mutable indirections in<br>
parameters -- and this includes delegates), then func() is guaranteed to<br>
never cause side-effects outside its caller. Therefore, it should be<br>
permissible to mark func() as pure.<br>
<br>
//<br>
<br>
Why is this important? Well, ultimately the motivation for pushing the<br>
envelope in this direction is due to functions of this sort:<br>
<br>
void toString(scope void delegate(const(char)[]) dg) {<br>
dg(...);<br>
}<br>
<br>
By allowing this function to be marked pure, we permit it to be called<br>
from pure code (which I proved in the above discussion as actually<br>
pure). Or, put another way, we permit template functions that call<br>
toString with a delegate that updates a local variable to be inferred as<br>
pure. This allows more parts of std.format to be pure, which in turn<br>
expands the usability of things like <a href="http://std.conv.to" target="_blank">std.conv.to</a> in pure code.<br>
Currently, to!string(3.14f) is impure due to std.format ultimately<br>
calling a toString function like the above, but there is absolutely no<br>
reason why computing the string representation of a float can't be made<br>
pure. Implementing this proposal would resolve this problem.<br>
<br>
Besides, expanding the scope of purity allows much more D code to be<br>
made pure, thus increasing purity-based optimization opportunities.<br>
<br>
So, in a nutshell, my proposal is:<br>
<br>
- Functions that, besides invoking a delegate parameter, are pure,<br>
should be allowed to be marked as pure.<br>
<br>
- Template functions that, besides invoking a delegate parameter,<br>
perform no impure operations should be inferred as pure.<br>
<br>
- A function that takes a delegate parameter cannot be strongly pure<br>
(but can be weakly pure), unless the delegate itself is pure.<br>
(Rationale: the delegate parameter potentially involves arbitrary<br>
references to the outside world, and thus cannot be strongly pure.)<br>
<span class="HOEnZb"><font color="#888888"><br>
<br>
T<br>
<br>
--<br>
Gone Chopin. Bach in a minuet.<br>
</font></span></blockquote></div><br></div>