Hacker News Reader

Comment by lambdasquirrel | Hacker News Reader

I think it's worth revisiting elementary algebra, because the way most of us learned it in grade school doesn't really do it justice.

With that said, we abandoned `ab = ba` because it's not useful for e.g. linear algebra. Elementary algebra is a very specific (but very useful) mathematical "DSL" over the reals. It's also not necessarily going to help you learn to reason about the kinds of abstractions you have whilst programming, per se, because we can't reverse `a . b` to `b . a` when we code either.

Make no mistake, this is a knowledge for knowledge's sake endeavor. A liberal arts of the STEM fields, if you will.

View on HN

Commutativity has been abandoned? What?! Nothing could be farther from the truth!

The requirement for order independence is literally everywhere … where would we be without being able to add or do set unions or lattice joins without fear of getting the order wrong?! Imagine getting two different waveforms when adding one to the other, depending on the order!

Order independence is not a property of general-purpose programming. As much as we'd love for that to go away, it is very much a reality of day-to-day programmers.

There's plenty of commutative operations in everyday programming.

a = f(c) b = g(d)

can be rearranged if f and g take different input data, and calling independent functions is something seen literally everywhere in programming. Optimizing compilers often take advantage of that.

Not sure what you mean by it not being a property of general-purpose programming. Do you mean it as, "I don't have to account for it in my day-to-day work"?

If so, I agree with you, but not quite in the way you mean (I think). We don't account for it just as fish don't have to account for water. The fact that you can swap two rows in an excel file and have the results be unchanged is a property that we just take for granted. It needs to be pointed out how remarkable it is, because there are situations where this doesn't work. Debits and credits in finance are not commutative because of overdraft limits. I'm sure you know all this, so I'm curious what you really mean.

I think the argument is more that commutivity of operations is context-dependent, even when the operation is written as multiplication. For example, knowing whether the terms of a multiplication can be commuted requires knowing whether the operands are scalars or matrices.

None of the common numeric systems in use on computers are commutative. IEEE-754 floating point is not. Integer types have over- and under-flow.

Sure, but the GP alluded to "general purpose programming" in a separate comment, by which I take it they meant something like conventional python/Java code where one uses signed integers and doesn't worry about under/overflow.

Integer overflows/underflows don't affect commutativity, unless you refer to undefined behavior, which is...undefined and found only in C and C++ among common languages. 2's complement integer arithmetic is commutative for both addition and multiplication.

Thanks to BeetleB for pointing out that addition in IEEE floats is indeed commutative (I originally claimed "+0 + -0 = +0 vs. -0 + +0 = -0" which is incorrect).

As for IEEE-754 floats, addition is commutative as long as you don't care about exact bit patterns:

NaN + NaN may return different bit patterns. The result is still NaN, so the only way you can tell this apart is by bit-casting floats to ints or byte arrays.

Multiplication over floats is also commutative modulo the caveat above.

> +0 + -0 = +0 vs. -0 + +0 = -0

These are not exceptions.

First, I will note that your result above depends on the rounding mode.

Second, IEEE 754 mandates that +0 and -0 are equal (i.e. any equality operator should return True when comparing these two). Therefore both expressions are equal.

NaN has several representations in bits, but they are all "equal" to one another.[1] If an operation gives you NaN, then so will doing it commutatively. It doesn't matter that the underlying bits are the same.

[1] Except for the signaling aspect. But I believe that is preserved in commutative operations.

You're right, producing +/- 0 depends on the rounding mode and it is commutative, I forgot about that completely. I edited my comment to fix that claim.

Also, yes, +0 == -0, but they can produce different results when used in the same expression, so the distinction does matter (although this doesn't affect commutativity, which is the larger point). For example, let f(x) = 1 / x. Then f(+0) = +inf, f(-0) = -inf.

I also agree with you about NaN, that's why I mentioned having to go outside floating point numbers (bit-casting).

> (I originally claimed "+0 + -0 = +0 vs. -0 + +0 = -0" which is incorrect)

Specifically, (-0.0) + (+0.0) = (+0.0) + (-0.0) = +0.0 (assuming round-to-nearest-or-even). OTOH, (-0.0) + (-0.0) = -0.0. This has nothing to do with +0.0 == -0.0 for comparison, addition just is commutative outright[0].

0: Pedantically, I'm not sure IEEE-754 requires the specific choice of which NaN you get when you do `some_nan + a_different_nan` versus `a_different_nan + some_nan` to be commutative, but it should.

Actually, they all are. They are not associative.

If a + b results in an overflow, so will b + a.

Thanks - I got that mixed up.

Commutativity is important for e.g. parallel programming. See e.g. <https://youtu.be/dPK6t7echuA>.

In the context of linear algebra, it would also be good for folks to know that matrix multiplication (/linear transformation composition) is not commutative.

Isn’t it more often associativity that is required for parallel programming? Being able to parallelize “a+b+c+d” only requires associativity to order the operations as “(a+b) + (c+d)”. Sure, there’s additional benefits for memory locality if you can rearrange the term to “(a+c) + (b+d)”, assuming that the four terms are stored in contiguous memory and each sum is computed with vector operations, but that’s not strictly required for parallelization.

In parallel programming, subcomputations may complete out of order. The ability to combine those subcomputations in any order can be pretty useful!

That, though, is associativity, not commutativity.

In FP arithmetic, operations are commutative, not associative.

If you receive b before a and combine them as b*a, that's commutative. Both properties are useful in parallel programming, but you may only need one in a specific case, depending on your application.

Both are important. I replied to a comment about commutativity, so I focused on that.

agree. arithmetic in computer languages do not have a theoretical basis that matches the theory of arithmetic in standard algebra. for example,

if a = 0.3 b=0.4 and c=5 as f32 in rust, then the following "well known results" from the article are all false:

   (b) a+(b+c) = (a+b)+c is false
   (d) a*(b+c) = a*b+a*c is false
   (f) (ab)^c = a^c b^c is false
   (g) a^b a^c = a^(b+c) is false
   (h) (a^b)^c = a^(b*c) is false

https://play.rust-lang.org/?version=stable&mode=debug&editio...

That particular part glossed over the details. Commutativity is a property of some groups and not others. It is a property of the "normal" numbers, so we all learn it in school. But there are lots of groups that aren't commutative.

Well there goes the whole CRDT thing...

Reply on news.ycombinator.com