www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Rewrite rules for ranges

reply "bearophile" <bearophileHUGS lycos.com> writes:
When you use UFCS chains there are many coding patterns that 
probably are hard to catch for the compiler, but are easy to 
optimize very quickly:

.sort().group.canFind => binary search

.sort().front => .reduce!min

.reverse.reverse => id

.reverse.back => .front

If the filtering and mapping functions are pure nothrow:
.map.filter => .filter.map

.map(a).map(b) => .map(compose(a, b))

and so on.

Such sub-optimal patterns can be written by programmers that are 
not caring a lot about performance, by mistake, or after inlining.

In Haskell this is so common that GHC has a feature named rewrite 
rules:

https://downloads.haskell.org/~ghc/6.12.2/docs/html/users_guide/rewrite-rules.html

https://www.haskell.org/haskellwiki/GHC/Using_rules

Such rules are simpler to do in Haskell because the code is much 
more pure compared to usual D code. But perhaps the same is 
possible and useful in D too.

Currently some rewrite rules are present inside the Phobos ranges.

Bye,
bearophile
Dec 20 2014
next sibling parent "Matthias Bentrup" <matthias.bentrup googlemail.com> writes:
On Saturday, 20 December 2014 at 14:16:05 UTC, bearophile wrote:
 If the filtering and mapping functions are pure nothrow:
 .map.filter => .filter.map
I think that one doesn't work.
Dec 20 2014
prev sibling next sibling parent reply "weaselcat" <weaselcat gmail.com> writes:
Seems like something that would fit in well with dscanner.
Dec 20 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
weaselcat:

 Seems like something that would fit in well with dscanner.
Nope. It's not a bug for the programmer, it's an optimization pass for the compiler. And it should work after inlining. Bye, bearophile
Dec 20 2014
parent "Daniel Murphy" <yebbliesnospam gmail.com> writes:
"bearophile"  wrote in message news:rrtewrwyiuhmkvmhfkuk forum.dlang.org...

 Seems like something that would fit in well with dscanner.
Nope. It's not a bug for the programmer, it's an optimization pass for the compiler. And it should work after inlining.
It's not a programmer bug, but that doesn't mean a tool to suggest possible optimizations and point out potential performance bottlenecks wouldn't be useful.
Dec 24 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Saturday, 20 December 2014 at 14:16:05 UTC, bearophile wrote:
 In Haskell this is so common that GHC has a feature named 
 rewrite rules:
Pure is fully based on term rewriting: http://purelang.bitbucket.org/
Dec 20 2014
prev sibling next sibling parent reply "renoX" <renozyx gmail.com> writes:
On Saturday, 20 December 2014 at 14:16:05 UTC, bearophile wrote:
 When you use UFCS chains there are many coding patterns that 
 probably are hard to catch for the compiler, but are easy to 
 optimize very quickly:
[cut]
 .reverse.reverse => id
.reverse.reverse is a coding pattern?? ;-) renoX
Dec 22 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
renoX:

 .reverse.reverse is a coding pattern??
Yes, similar patterns can come out after inlining. Bye, bearophile
Dec 22 2014
prev sibling parent "Daniel Murphy" <yebbliesnospam gmail.com> writes:
"bearophile"  wrote in message news:tgxtiqcfxfhpmubfkpzt forum.dlang.org... 

 But perhaps the same is possible and useful in D too.
http://forum.dlang.org/thread/qeytzeqnygxpocywyifp forum.dlang.org
Dec 24 2014