Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
1–10 of 36 posts
Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
#2How does this compare to stream fusion? http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7...
Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
#3Interesting article. Not sure if it meets the of the "Show HN" guidelines -- there is nothing for users to try out or play with. If it is still withing the window, maybe change the title. If not, maybe email the moderators.
Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
#4How does this compare to stream fusion? http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7...
Ah, I knew that HN would tell me what I should be reading! I've only been able to spend a few minutes reading this one, but it looks to me like the first focus there is on eliminating intermediate containing structures, with some interesting opportunities for optimization afterwards. Their stream definition of fold(l/r) is still recursive, so I don't think it would be able to pull, for example, the incr() outside the reduce in my first example of "reduce(max, map(incr, l))"
I think the approaches might be complimentary, actually; you might apply the higher level transformations I describe first and use a stream approach to implement the resulting chain of operations.
Going to need to do a deeper investigation later today, but, anything else I should be looking at?
Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
#5Interesting article. Not sure if it meets the of the "Show HN" guidelines -- there is nothing for users to try out or play with. If it is still withing the window, maybe change the title. If not, maybe email the moderators.
Thanks! I have a link to code written in Maude at the very bottom; The code needs so much explanation though. Perhaps I'll highlight the code link at the top of the article?
Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
#6Interesting article. Not sure if it meets the of the "Show HN" guidelines -- there is nothing for users to try out or play with. If it is still withing the window, maybe change the title. If not, maybe email the moderators.
Thanks! I have a link to code written in Maude at the very bottom; The code needs so much explanation though. Perhaps I'll highlight the code link at the top of the article?
Or post a clickable link here in the thread? Explaining the code might be an opportunity to create a rough draft of something more polished. A bit of background on Maude might be nice too. Save readers from Googling and maybe help people understand why it was used. All things that tend to be "intellectually interesting."
Anyway, I was a bit philosophically torn since the content tends toward mathematical/algorithmic and made me wonder what does it mean to play around with mathematics/algorithms?
Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
#7Interesting article. Not sure if it meets the of the "Show HN" guidelines -- there is nothing for users to try out or play with. If it is still withing the window, maybe change the title. If not, maybe email the moderators.
Thanks! I have a link to code written in Maude at the very bottom; The code needs so much explanation though. Perhaps I'll highlight the code link at the top of the article?
Yes, that is just the trick. Great post.
Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
#8How do we make compilers smart enough to know that “sum(reverse(x))” can be rewritten to “sum(x)”.
That examle is pretty easy; you apply a pattern match to the tree which looks for the pattern (sum (reverse ?var)) and rewrites it to (sum ?var).
In Common Lisp, we would use define-compiler-macro on the sum function which looks for the argument form being (reverse whatever), in which case the macro returns the form (sum whatever).
Not so fast, though; order of summing matters in floating-point! And over integers too, in the presence of overflows (in junk languages without bignums). That is to say, if we add together three or more integers, the arithmetic result can be in range of the type, but some orders might overflow, whereas others do not.
Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
#9Earlier quoted context omitted.
Thanks! I have a link to code written in Maude at the very bottom; The code needs so much explanation though. Perhaps I'll highlight the code link at the top of the article?
Or post a clickable link here in the thread? Explaining the code might be an opportunity to create a rough draft of something more polished. A bit of background on Maude might be nice too. Save readers from Googling and maybe help people understand why it was used. All things that tend to be "intellectually interesting." Anyway, I was a bit philosophically torn since the content tends toward mathematical/algorithmic…
Totally; great point. My code is here:
https://github.com/pschanely/wf-optimizer/blob/master/demo.m...
Maude is a programming language based on rewriting: http://maude.cs.illinois.edu/w/index.php
It's pretty wild; your code doesn't "execute" in the traditional sense; instead patterns match the code and transform it repeatedly until it reaches a "normal form" - one that cannot be rewritten further.
Maude is handy for playing with optimizers, because you very often want to specify behavior in terms of patterns (when you see these functions together, replace them with this...)
Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
#10How do we make compilers smart enough to know that “sum(reverse(x))” can be rewritten to “sum(x)”. That examle is pretty easy; you apply a pattern match to the tree which looks for the pattern (sum (reverse ?var)) and rewrites it to (sum ?var). In Common Lisp, we would use define-compiler-macro on the sum function which looks for the argument form being (reverse whatever), in which case the macro returns the form (su…
Great observations. For the purposes of this exploration, I am entirely assuming arbitrary precision integers (and the math geek in me is really enjoying your use of the adjective "junk", above).
Bigger picture, I want to rewrite "sum(reverse(x))" without explicitly saying so. How do we optimize that expression using the definitions of sum and reverse? Note that in my discussion of this in my second example, I am inconsistent here: I expand the definition of reverse() but treat sum() as a primitive. That said, I am pretty sure that the example still works if you substitute the appropriate definition of sum as "reduce(add,x)"; the derivation is just longer.