4 ms·
Is it possible to write an optimizer for something like `sum (filter is_even (range 0 100))` into a for loop, as to avoid materializing 2 lists in memory?
by lalaithion 4y ago
Is it possible to write an optimizer for something like `sum (filter is_even (range 0 100))` into a for loop, as to avoid materializing 2 lists in memory?
- sitkack 4y agoDoesn't inlining handle that case directly?
- ehatti 4y agoYes. As I’ve said elsewhere, the system is not limited to simple term rewrites.
- lalaithion 4y agoIs there an example of such a program? I don't see anything like that in the github repo.
- ehatti 4y agoUnfortunately not! Embarrassingly, I haven't implemented pattern matching yet, which means functions like `sum` and `filter` can't be written. So far all my effort has gone towards the metaprogramming system. Bugfixing has me occupied at the moment, but after that I plan on doing pattern matching.
- tonyg 4y agoYou might enjoy this paper, which presents "stream fusion", a technique which can do what you're talking about as well as a bunch of other cool stuff: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7... "Stream Fusion: From Lists to Streams to Nothing at All." Duncan Coutts, Roman Leshchinskiy, Don Stewart. ICFP 2007.
- cryptonector 4y agoYes. I knew this as list fusion. Note that Rust doesn't need to do this because of the way `iter_into()` and mapping works. List fusion boils down to removing interior `.collect().iter_into()`. There is something to be said for designing APIs so that you don't need such rewrite rules, though, of course, the need comes up eventually anyways, so rewrite rules end up being kinda necessary.