www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - inverse

reply "Daniel N" <ufo orbiting.us> writes:
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)
Feb 25 2015
next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
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.
Feb 25 2015
parent "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
Short messy recent attempt at implementing some things like this 
at a library level:

https://github.com/evenex/atl/blob/master/source/main.d
Feb 25 2015
prev sibling parent reply "Xinok" <xinok live.com> writes:
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
Feb 25 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Feb 25 2015
next sibling parent "Xinok" <xinok live.com> writes:
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.
Feb 25 2015
prev sibling parent ketmar <ketmar ketmar.no-ip.org> writes:
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=20 case" generator and wasn't able to hit the bug with arrays up to=20 1_807_108_864 elements (which is almost the limit my box can handle). so=20 either phobos sort is immune, or we need REALLY big arrays to $#^ ^ it up.=
Feb 25 2015
prev sibling parent reply "Sativa" <Sativa Indica.org> writes:
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.
Feb 25 2015
parent "Xinok" <xinok live.com> writes:
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)
Feb 25 2015