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

21–30 of 36 posts

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

#21

Post by prodigal_erik »

kazinator wrote: post #19
rntz wrote: post #15

Earlier quoted context omitted.

> And over integers too, in the presence of overflows (in junk languages without bignums) I don't think this is true. Modular addition is commutative and associative. As long as the behavior of overflow is modular (as it is in 2's complement), order shouldn't matter. And if the behavior of overflow is to trap, then it should trap regardless of the order you add the numbers in. I guess if you care about the stack trac…

> And if the behavior of overflow is to trap, then it should trap regardless of the order you add the numbers in. How come? Suppose A + B doesn't trap, and if T0 = A + B, then T0 + C doesn't trap. Why should (A + B) + C trap?

Say you have a register whose range is -9..+9. (5-1)+5 doesn't trap but (5+5)-1 does.

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

#22

Post by kazinator »

prodigal_erik wrote: post #21
kazinator wrote: post #19

Earlier quoted context omitted.

> And if the behavior of overflow is to trap, then it should trap regardless of the order you add the numbers in. How come? Suppose A + B doesn't trap, and if T0 = A + B, then T0 + C doesn't trap. Why should (A + B) + C trap?

Say you have a register whose range is -9..+9. (5-1)+5 doesn't trap but (5+5)-1 does.

I understand how to make an example of this; the question is why should (5-1)+5 trap, just because (5+5)-1 does.

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

#23

Post by _lm_ »

For the Map-Reduce transformation, you require f(r(a,b)) = r(f(a),f(b)). This is equivalent to requiring r to be a homomorphism, I think.

You could probably generalize that condition to situations where f can be lifted over the output of r so you don't have to require that r's output type is the same as its input.

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

#24

Post by rntz »

kazinator wrote: post #19
rntz wrote: post #15

Earlier quoted context omitted.

> And over integers too, in the presence of overflows (in junk languages without bignums) I don't think this is true. Modular addition is commutative and associative. As long as the behavior of overflow is modular (as it is in 2's complement), order shouldn't matter. And if the behavior of overflow is to trap, then it should trap regardless of the order you add the numbers in. I guess if you care about the stack trac…

> And if the behavior of overflow is to trap, then it should trap regardless of the order you add the numbers in. How come? Suppose A + B doesn't trap, and if T0 = A + B, then T0 + C doesn't trap. Why should (A + B) + C trap?

Ah, good point! I was thinking of unsigned overflow, but signed overflow is a different matter, as pointed out elsewhere in this thread. I retract my statement about trapping overflow.

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

#25

Post by pschanely »

_lm_ wrote: post #23

For the Map-Reduce transformation, you require f(r(a,b)) = r(f(a),f(b)). This is equivalent to requiring r to be a homomorphism, I think. You could probably generalize that condition to situations where f can be lifted over the output of r so you don't have to require that r's output type is the same as its input.

Unfortunately, I took barely enough grad school classes to be dangerous! It's worth clarifying that the lifting of f through r can change r (to, say r'), in which case, yes, f is a homomorphism from an algebra with r' to an algebra with r. (hopefully I got that right?)

I am curious about the idea that the inputs and outputs of r may not need to be of the same type, and want to investigate further (help is appreciated!). Since r is given to reduce(), at least one of its inputs must match its output, depending on how you define reduce(). Haskell's fold(l/r) permit the non-accumulator side to differ in type from the output, but the output must match the accumulator side. I think some similar transformation may apply to folds, but haven't thought about it enough.

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

#26

Post by AnimalMuppet »

kazinator wrote: post #20
AnimalMuppet wrote: post #17

Earlier quoted context omitted.

Seconded. I can't see any encoding system that has fixed-sized integers (and therefore can overflow) where the result of addition is order-dependent. I mean, I'm sure you could design one. But if there's an example of an actually-used encoding that has this property, I'd like to hear it. (And as you said, using floats doesn't count...)

The result of the addition isn't order dependent; whether or not there is overflow is order-dependent. I put that into my original comment for the sake of completeness, in an additional edit after the floating-point remark. Ironically, it was to fend off smart-alecky follow-ups about how I forgot integer overflow. A higher-level language should have a plus operator/function that traps integer overflows if it doesn't…

I was going to ask, once again, how that is possible, but I think I figured it out while reading this, though you don't explicitly state it.

It can happen if some of the numbers are negative. For a simple example, if overflow occurs at 100, 50+60-20 overflows, but 50-20+60 does not.

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

#27

Post by pschanely »

ericbb wrote: post #18

This approach is strongly reminiscent of abstract algebra; for example, the Map-Reduce Transformation example seems to be(?) justified exactly when f is an isomorphism over r. I've been thinking along somewhat similar lines but I've been looking at it from the perspective of introduction and elimination rules, as found in type theory. If your compiler can find a transformation that brings an intro form and an elim fo…

Yes! I think perhaps that f needs only to be a homomorphism instead of an isomorphism, but I don't trust myself enough to make such a claim definitively :)

Always curious to follow people doing compiler work; loop me in, yeah?

And, just watched that Wadler talk; it's good stuff. Of course, it sounds like his scenario is like: "there is a way to do the transformation, you just have to find it," and in my case, it's more like: "there might or might not be an algebra in which f acts as a homomorphism, and, even if there is, you may not have the transformations you need to determine it!"

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

#28

Post by kazinator »

AnimalMuppet wrote: post #26
kazinator wrote: post #20

Earlier quoted context omitted.

The result of the addition isn't order dependent; whether or not there is overflow is order-dependent. I put that into my original comment for the sake of completeness, in an additional edit after the floating-point remark. Ironically, it was to fend off smart-alecky follow-ups about how I forgot integer overflow. A higher-level language should have a plus operator/function that traps integer overflows if it doesn't…

I was going to ask, once again, how that is possible, but I think I figured it out while reading this, though you don't explicitly state it. It can happen if some of the numbers are negative . For a simple example, if overflow occurs at 100, 50+60-20 overflows, but 50-20+60 does not.

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 that specific case is fine over integers (optimizing away reverse).

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

#29

Post by ericbb »

pschanely wrote: post #27
ericbb wrote: post #18

This approach is strongly reminiscent of abstract algebra; for example, the Map-Reduce Transformation example seems to be(?) justified exactly when f is an isomorphism over r. I've been thinking along somewhat similar lines but I've been looking at it from the perspective of introduction and elimination rules, as found in type theory. If your compiler can find a transformation that brings an intro form and an elim fo…

Yes! I think perhaps that f needs only to be a homomorphism instead of an isomorphism, but I don't trust myself enough to make such a claim definitively :) Always curious to follow people doing compiler work; loop me in, yeah? And, just watched that Wadler talk; it's good stuff. Of course, it sounds like his scenario is like: "there is a way to do the transformation, you just have to find it," and in my case, it's mo…

That's funny. I was thinking isomorphism because you postulate an inverse, which homomorphisms don't always have. But the identity doesn't depend on f being invertible. You could just have a rule:

If f is a homomorphism with respect to r, then reduce(r, map(f, l)) = f(reduce(r, l)).

The rule can be proven without reference to an inverse for f so isn't it enough to just add such a rewrite rule to your optimizer? (Now I'm not sure what the inversion trick accomplishes?).

> Always curious to follow people doing compiler work; loop me in, yeah?

norstrulde.org and twitter.com/ericbb

> "there might or might not be an algebra in which f acts as a homomorphism, and, even if there is, you may not have the transformations you need to determine it!"

To my way of interpreting it, the algebra is determined by r, which is given. You might not know whether f is a homomorphism with respect to r and it'd be tricky to figure that out by inspecting the definitions for f and r but if you have a table built in advance that characterizes functions in relation to each other (incr is a homomorphism with respect to max, etc.), then you can drive your rewrite engine using that table... So I wouldn't say that you want to use transformations to determine if f is a homomorphism but rather that you want to use the fact that f is a homomorphism to decide which transformations are applicable. Does that make sense?

Edit: I guess, more generally, you could have a relation with the form homomorphism(f:a->b, q:a->a->a, r:b->b->b) which justifies the transformation reduce(r, map(f, l)) -> f(reduce(q, l)).

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

#30

Post by dllthomas »

kazinator wrote: post #28
AnimalMuppet wrote: post #26

Earlier quoted context omitted.

I was going to ask, once again, how that is possible, but I think I figured it out while reading this, though you don't explicitly state it. It can happen if some of the numbers are negative . For a simple example, if overflow occurs at 100, 50+60-20 overflows, but 50-20+60 does not.

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]
Post reply on HN