Just throwing an idea out there... How about using annotations to teach the compiler which functions are inverses of each-other, in order to facilitate optimizing away certain redundant operations even if they are located inside a library(i.e. no source).

A little pseudo-code for illustrational purposes, in case my above text is incomprehensible:

void inc() pure nothrow @inverse(dec)
void dec() pure nothrow @inverse(inc)

void swap(T)(ref T lhs, ref T rhs) pure nothrow @inverse(swap!T)

On Wed, Feb 25, 2015 at 09:25:47PM +0000, Daniel N via Digitalmars-d wrote:
> Just throwing an idea out there... How about using annotations to teach the compiler which functions are inverses of each-other, in order to facilitate optimizing away certain redundant operations even if they are located inside a library(i.e. no source).
> 
> A little pseudo-code for illustrational purposes, in case my above text is incomprehensible:
> 
> void inc() pure nothrow @inverse(dec)
> void dec() pure nothrow @inverse(inc)
> 
> void swap(T)(ref T lhs, ref T rhs) pure nothrow @inverse(swap!T)

I like this idea. It could help ARC by not requiring specific language support for ARC, at least as far as eliding redundant inc/dec pairs are concerned, but allowing a library refcounting type to hint to the optimizer that if inc/dec of the count occurs in pairs, the compiler can elide them if nobody else looks at the refcount in the interim..

It also helps algebra libraries where repeating a self-inverting operation can be automatically elided, thereby simplifying complex expressions a bit and perhaps allowing further optimizations.

For the latter, though, it would be even better if other identities are
definable, for example @reflexive for indicating that func(x,x) == true,
@symmetric for indicating func(x,y) == func(y,x), and so on.

Not sure how likely it is that this will actually make it into the language, though. Recently there seems to be a lot of resistance against adding new features that don't have sufficiently wide applicability.


T

-- 
People tell me that I'm paranoid, but they're just out to get me.

Short messy recent attempt at implementing some things like this at a library level:

https://github.com/evenex/atl/blob/master/source/main.d

On Wednesday, 25 February 2015 at 21:25:49 UTC, Daniel N wrote:
> Just throwing an idea out there... How about using annotations to teach the compiler which functions are inverses of each-other, in order to facilitate optimizing away certain redundant operations even if they are located inside a library(i.e. no source).
>
> A little pseudo-code for illustrational purposes, in case my above text is incomprehensible:
>
> void inc() pure nothrow @inverse(dec)
> void dec() pure nothrow @inverse(inc)
>
> void swap(T)(ref T lhs, ref T rhs) pure nothrow @inverse(swap!T)

I like the idea but feel that it's application is too narrow. I prefer features which are more general and offer greater flexibility. I believe I've read somewhere that some [functional] languages define common patterns and equivalent substitutions for optimization purposes.

inc(dec(x)) -> x
dec(inc(x)) -> x
cos(x)^^2 + sin(x)^^2 -> 1

On 2/25/15 4:55 PM, Xinok wrote:
> On Wednesday, 25 February 2015 at 21:25:49 UTC, Daniel N wrote:
>> Just throwing an idea out there... How about using annotations to
>> teach the compiler which functions are inverses of each-other, in
>> order to facilitate optimizing away certain redundant operations even
>> if they are located inside a library(i.e. no source).
>>
>> A little pseudo-code for illustrational purposes, in case my above
>> text is incomprehensible:
>>
>> void inc() pure nothrow @inverse(dec)
>> void dec() pure nothrow @inverse(inc)
>>
>> void swap(T)(ref T lhs, ref T rhs) pure nothrow @inverse(swap!T)
>
> I like the idea but feel that it's application is too narrow. I prefer
> features which are more general and offer greater flexibility. I believe
> I've read somewhere that some [functional] languages define common
> patterns and equivalent substitutions for optimization purposes.
>
> inc(dec(x)) -> x
> dec(inc(x)) -> x
> cos(x)^^2 + sin(x)^^2 -> 1

Since you're here, do you plan to fix stable sort as recently discussed? -- Andrei

On Thursday, 26 February 2015 at 00:56:02 UTC, Xinok wrote:
> On Wednesday, 25 February 2015 at 21:25:49 UTC, Daniel N wrote:
>> Just throwing an idea out there... How about using annotations to teach the compiler which functions are inverses of each-other, in order to facilitate optimizing away certain redundant operations even if they are located inside a library(i.e. no source).
>>
>> A little pseudo-code for illustrational purposes, in case my above text is incomprehensible:
>>
>> void inc() pure nothrow @inverse(dec)
>> void dec() pure nothrow @inverse(inc)
>>
>> void swap(T)(ref T lhs, ref T rhs) pure nothrow @inverse(swap!T)
>
> I like the idea but feel that it's application is too narrow. I prefer features which are more general and offer greater flexibility. I believe I've read somewhere that some [functional] languages define common patterns and equivalent substitutions for optimization purposes.
>
> inc(dec(x)) -> x
> dec(inc(x)) -> x
> cos(x)^^2 + sin(x)^^2 -> 1

Which would exactly be the result of what Daniel is talking about except you are adding invariance which is a harder problem yet can be taken care of by the programmer(you would never intentionally write cos(x)^2 + sin(x)^2 for anything since it is equal to 1 and 1 is more efficient to compute).

The problem is one of composition and it is difficult in real circumstances since compositions may not be simply ordered.

e.g., what if you have

inc(foo(dec(x))

?

In this case one can't simplify because one doesn't know what foo does.

Hence, to do it properly one would have to create a whole compositional system. e.g., @linear, @nonlinear, @additive, @commutative, etc...

e.g., if we new foo was linear then we could simplify the above to foo(x).

...and, as you hinted at, most functions are non-linear and therefor will make @inverse nearly useless.


I suppose, though, one might be able to do something like setup @inverse functions for actions.

e.g., user clicks on button X. The inverse then is sort of an "undo" of that.

In an undo system one expects every action to be "linear"(have an inverse)... Hence it might be useful in such circumstances.

On Thursday, 26 February 2015 at 01:40:32 UTC, Andrei Alexandrescu wrote:
> Since you're here, do you plan to fix stable sort as recently discussed? -- Andrei

While the fix seems straightforward, I haven't taken the time to study the problem. I plan to do so and if I feel confident that I can fix the issue and provide a test case, then I'll make a pull request. That's the best I can say for now.

On Thursday, 26 February 2015 at 02:05:25 UTC, Sativa wrote:
> On Thursday, 26 February 2015 at 00:56:02 UTC, Xinok wrote:
>> I like the idea but feel that it's application is too narrow. I prefer features which are more general and offer greater flexibility. I believe I've read somewhere that some [functional] languages define common patterns and equivalent substitutions for optimization purposes.
>>
>> inc(dec(x)) -> x
>> dec(inc(x)) -> x
>> cos(x)^^2 + sin(x)^^2 -> 1
>
> Which would exactly be the result of what Daniel is talking about except you are adding invariance which is a harder problem yet can be taken care of by the programmer(you would never intentionally write cos(x)^2 + sin(x)^2 for anything since it is equal to 1 and 1 is more efficient to compute).

Not intentionally, but consider that D is a very generative language. Templates and string mixins are used heavily. However, the generated code is usually pretty generic so little things like trig identities may appear in the code which the compiler doesn't know how to optimize away. Some C++ compilers make assumptions about standard library functions so techniques similar to this are not unheard of.

> The problem is one of composition and it is difficult in real circumstances since compositions may not be simply ordered.
>
> e.g., what if you have
>
> inc(foo(dec(x))
>
> ?
>
> In this case one can't simplify because one doesn't know what foo does.
>
> Hence, to do it properly one would have to create a whole compositional system. e.g., @linear, @nonlinear, @additive, @commutative, etc...
>
> e.g., if we new foo was linear then we could simplify the above to foo(x).
>
> ...and, as you hinted at, most functions are non-linear and therefor will make @inverse nearly useless.

That almost seems too complicated, like it would require a complete CAS built into the compiler. Some functions don't have clearly defined inverses as well, such as x^^3. Then x^^2 is only invertible if you limit the domain and range to x >= 0.

>
> I suppose, though, one might be able to do something like setup @inverse functions for actions.
>
> e.g., user clicks on button X. The inverse then is sort of an "undo" of that.
>
> In an undo system one expects every action to be "linear"(have an inverse)... Hence it might be useful in such circumstances.

I wouldn't use the term "linear" to mean "invertible". A linear function is one such that:
f(c*a + b) = c*f(a) + f(b)

On Wed, 25 Feb 2015 17:40:31 -0800, Andrei Alexandrescu wrote:

> Since you're here, do you plan to fix stable sort as recently discussed? -- Andrei

it's not necessarily so fubared as article says. i ported their java "bad case" generator and wasn't able to hit the bug with arrays up to 1_807_108_864 elements (which is almost the limit my box can handle). so either phobos sort is immune, or we need REALLY big arrays to $#^@^ it up.