View mode: basic / threaded / horizontal-split · Log in · Help
January 18, 2012
Pure functions and delegates
So, I was quite impressed with D's pureness system, and was
experimenting a bit with it. Then I discovered that delegates are
impure, which seems reasonable since there's no way to know what a
delegate might do. But *if* the compiler verifies that a particular
delegate is (weakly) pure in the context of the function that passed it,
then couldn't the function that it gets passed to be declared pure as
well?

The context is this:

	class MyCollection {
		...
		void opApply(int delegate(const ref int n) cb) const {
			...
			if (cb(...)) { ... }
			...
		}
		...
		int[] enumerate() {
			int[] list;
			foreach (n; this) {
				list ~= n;
			}
			return list;
		}
	}

Is there a way to convince the compiler that enumerate() can be marked
'pure' even though opApply() can't, in general, be pure because it
doesn't know what the delegate does?

Technically, enumerate() is weakly pure, because its delegate does not
touch anything outside of its scope, and given this particular delegate,
opApply() also is weakly pure. In other words, opApply()'s pureness
depends on the delegate passed to it. So if there was a way for the
compiler to check that yes, opApply() is (weakly) pure except for the
part that calls the delegate (perhaps using some kind of "conditionally
pure" attribute?), then it should, in theory, be possible to verify that
yes, the delegate that enumerate() passes to opApply() does not violate
pureness, so enumerate() can be labelled 'pure'.

The trouble is, given the current state of things, there is no way to
implement enumerate() in a pure way, short of duplicating most of
opApply()'s code and substituting the line that calls the delegate.
Which is a rather ugly workaround. But otherwise, MyCollection cannot be
used inside a (strongly) pure function unless it avoids using opApply()
and enumerate() altogether, even if the container never escapes the pure
function's scope. This is quite a major limitation IMHO.


T

-- 
He who laughs last thinks slowest.
January 18, 2012
Re: Pure functions and delegates
On 01/18/2012 04:40 AM, H. S. Teoh wrote:
> So, I was quite impressed with D's pureness system, and was
> experimenting a bit with it. Then I discovered that delegates are
> impure, which seems reasonable since there's no way to know what a
> delegate might do. But *if* the compiler verifies that a particular
> delegate is (weakly) pure in the context of the function that passed it,
> then couldn't the function that it gets passed to be declared pure as
> well?
>
> The context is this:
>
> 	class MyCollection {
> 		...
> 		void opApply(int delegate(const ref int n) cb) const {
> 			...
> 			if (cb(...)) { ... }
> 			...
> 		}
> 		...
> 		int[] enumerate() {
> 			int[] list;
> 			foreach (n; this) {
> 				list ~= n;
> 			}
> 			return list;
> 		}
> 	}
>
> Is there a way to convince the compiler that enumerate() can be marked
> 'pure' even though opApply() can't, in general, be pure because it
> doesn't know what the delegate does?
>
> Technically, enumerate() is weakly pure, because its delegate does not
> touch anything outside of its scope, and given this particular delegate,
> opApply() also is weakly pure. In other words, opApply()'s pureness
> depends on the delegate passed to it. So if there was a way for the
> compiler to check that yes, opApply() is (weakly) pure except for the
> part that calls the delegate (perhaps using some kind of "conditionally
> pure" attribute?), then it should, in theory, be possible to verify that
> yes, the delegate that enumerate() passes to opApply() does not violate
> pureness, so enumerate() can be labelled 'pure'.
>
> The trouble is, given the current state of things, there is no way to
> implement enumerate() in a pure way, short of duplicating most of
> opApply()'s code and substituting the line that calls the delegate.
> Which is a rather ugly workaround. But otherwise, MyCollection cannot be
> used inside a (strongly) pure function unless it avoids using opApply()
> and enumerate() altogether, even if the container never escapes the pure
> function's scope. This is quite a major limitation IMHO.
>
>
> T
>

I see two distinct issues here:

1.

int foo(int delegate(int) dg,x){return dg(x);}
int bar(int x)pure{foo(x=>x,x);} // error but would be ok

2.

int foo(int x)pure{
    int x;
    (y=>x=y)(2); // error but would be ok
    return x;
}

1. could be resolved by a simple purity wildcard, in the lines of inout. 
(auto pure? =))
2. could be resolved by extending the weakly pure rule to the context 
pointer of nested functions. Nested functions and delegates would need 
to be able to be declared 'const'. (indicating that they are not allowed 
to mutate anything through the context pointer.) delegate literals and 
nested template function instantiations would need const inference.
Top | Discussion index | About this forum | D home