Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Optimizing Higher Order Functions with Hypothetical Inverses

medium.com

Post reply on HN
Print view View original

31–36 of 36 posts

Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses

#31

Post by hawkice »

dllthomas wrote: post #30
kazinator wrote: post #28

Earlier quoted context omitted.

It's very hard to be aware of the numerous details you find obvious yourself when you're communicating. Also, by the way, I have an intuition that the issue might not specifically prevent the removal of a reverse operation. That is to say, if a series with some positives or negative integers does/doesn't overflow under a left fold, I have a hunch that it does/doesn't under a right fold. If this can be proven, then th…

[1, intmax, -1]

So, yes, one direction overflows and one doesn't, but as long as the contract says overflow works as two's compliment, the answer is the same. This is why not having undefined behavior is so useful.

Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses

#32

Post by btown »

pschanely wrote: post #16
js8 wrote: post #14

This is excellent, I was thinking about similar optimization using inverses: If one calculates some reduction over a data structure, and this reduction is group operator (so it has inverse, like addition), and this data structure is then updated, it may be easier to recalculate the reduction by updating the result through inverse than to recalculate the whole reduction again. For example, we are calculating sum over…

Thank you. And, heck yes, more people need to be talking about how to deal with computations that are largely repeated. That problem comes up all over the place. Couchdb had an interesting approach for this that did not require inverses: they persist intermediate reduce results, so that you can re-use nodes in the tree that haven't changed. So clever. http://horicky.blogspot.com/2008/10/couchdb-implementation.h...

Database indices (SQL and no) are similar in that regard - they are persisted so that a single insertion or update does not invalidate the entire index. Cache invalidation is a hard general problem, but easier when a closed system (like a database) is the only thing using its own cache, and the interface is much higher level.

Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses

#33

Post by dllthomas »

hawkice wrote: post #31
dllthomas wrote: post #30

Earlier quoted context omitted.

[1, intmax, -1]

So, yes, one direction overflows and one doesn't, but as long as the contract says overflow works as two's compliment, the answer is the same. This is why not having undefined behavior is so useful.

It doesn't have to be two's compliment - for any modular arithmetic, the answer will be the same.

But that's at a cost of giving up knowledge of whether it overflowed. In this case it overflows and underflows, when it does, an equal number of times, so there happens to be no problem. In some cases, all you care about is the answer modulo some number which jives well with your numbers' representation. In that case, there is also no problem.

In many cases, if there is a different number of overflows than underflows, you'd get the wrong answer without knowing it, and your answer is likely (but not guaranteed) to be very wrong when you do.

There are other approaches we can take. Overflow could saturate. In that case, we get the wrong answer in one direction here but it's only off by a little instead of a lot. Overflow could also trap, in which case we'd notice that we had risk of giving the wrong answer.

In either of these cases, we could not apply this optimization unless we allow for some measure of undefined behavior - which is why undefined behavior is so useful. It is absolutely the case that undefined behavior in a specification has significant drawbacks as well - but the issue at hand here is not the result of them.

Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses

#35

Post by joefkelley »

js8 wrote: post #14

This is excellent, I was thinking about similar optimization using inverses: If one calculates some reduction over a data structure, and this reduction is group operator (so it has inverse, like addition), and this data structure is then updated, it may be easier to recalculate the reduction by updating the result through inverse than to recalculate the whole reduction again. For example, we are calculating sum over…

I would love to see an analytics database system built on this idea. Let me define my "incoming" tables, and then define how other aggregated or transformed materialized views should be computed, and automatically update the downstream datasets based on changes in the input tables.

Let me define only "what" to compute, instead of spending all my time worrying about "how" and "when". Isn't that the point of declarative languages like SQL?

Re: Show HN: Optimizing Higher Order Functions with Hypothetical Inverses

#36

Post by pschanely »

Referenced in the paper panic suggested below ( https://news.ycombinator.com/item?id=11595273 ), and suggested to me directly by @mattcmd on twitter ( https://twitter.com/mattmcd/status/726342652845809664 ), there is something called the "fusion property of fold," which would explain transformations I'm discussing here applied to folds (sided reduce). From the paper ( http://www.cs.nott.ac.uk/~pszgmh/fold.pdf ), (and some minimal editorial substitution from me) we see that:

h(fold(g, w, l)) = fold(f, h(w), l)

if

h(g(x, y)) = f(x, h(y))

This is exciting because (1) it suggests the equivalent transformation for sided reduces (folds), and (2) fold is a more general operator than the others. My somewhat silly use of "hypothetical inverses" effectively just creates a goalpost to (1) constructively find the the function f, given g (or vice-versa) and (2) prove the necessary condition.

Very exciting.

Post reply on HN