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