Weekly edition Kernel Security Distributions Contact Us Search Archives Calendar Subscribe Write for LWN LWN.net FAQ Sponsors

Posted Apr 17, 2012 17:03 UTC (Tue) by butlerm (subscriber, #13312)

Posted Apr 17, 2012 17:32 UTC (Tue) by nybble41 (subscriber, #55106) [Link]

No, I'm pretty sure they meant "transitive". Commutative is (A == B) <=> (B == A). Transitive is (A == B) && (B == C) <=> (A == C).

> To be fair, == isn't transitive in Javascript either.
>
> 0 == ''; // true
> 0 == '0'; // true
> '' == '0'; // false

The first line is backwards, strictly speaking, but ('' == 0) is also true. Substituting that form, we have A = '', B = 0, and C = '0'. (A == B) and (B == C) are thus both true, but (A == C) is false, so the relation is not transitive.

Equality may not be commutative in all cases, either, but for that you would need different examples. All of the cases listed here are commutative.

Posted Apr 18, 2012 15:08 UTC (Wed) by k3ninho (subscriber, #50375) [Link]

Commutivity is more-often defined in terms of the sequence you use operators. It's not obvious, but Equality is the operator in your example. An alternative example: Commutative means that, for functions A:x->x, B:x->x: A(B(x)) == B(A(x)).

K3n.

Posted Apr 18, 2012 19:43 UTC (Wed) by dtlin (✭ supporter ✭, #36537) [Link]

Indeed. The word for a == bb == a is reflexive.

Posted Apr 18, 2012 20:18 UTC (Wed) by nybble41 (subscriber, #55106) [Link]

> Indeed. The word for a == b iff b == a is reflexive.

The answer is "both". The equality _relation_ is reflexive. The equality _operation_ is commutative.

> Commutative means that, for functions A:x->x, B:x->x: A(B(x)) == B(A(x)).

This doesn't fit any definition of "commutative" I was able to find. Every case I could locate involved the order of _operands_ to a single _binary_ function. Of course, you can turn you example into something like that, though with slightly different types, using higher-order functions (in pseudo-Haskell):

f1, f2 :: (a -> b) -> b
f1 = \f -> f A
f2 = \f -> f B
f1 (f2 (==)) == f2 (f1 (==))

but that is equivalent to the much simpler form:

(==) B A == (==) A B

or:

(B == A) == (A == B)

Posted Apr 19, 2012 22:55 UTC (Thu) by mmorrow (subscriber, #83845) [Link]

>> Commutative means that, for functions A:x->x, B:x->x: A(B(x)) == B(A(x)).

> This doesn't fit any definition of "commutative" I was able to find.
> Every case I could locate involved the order of _operands_ to a single _binary_ function.

The elusive binary operator here is function composition ;)

Posted Apr 19, 2012 23:14 UTC (Thu) by mmorrow (subscriber, #83845) [Link]

> The elusive binary operator here is function composition ;)

A reference for the interested being:
http://en.wikipedia.org/wiki/Centralizer_and_normalizer

Posted Apr 20, 2012 0:03 UTC (Fri) by nybble41 (subscriber, #55106) [Link]

>>> Commutative means that, for functions A:x->x, B:x->x: A(B(x)) == B(A(x)).
> The elusive binary operator here is function composition ;)

I thought you were presenting a general version of the commutative property, not a specialized version for function composition. That explains why I couldn't reconcile your example with other commutative operators (equality, addition, multiplication) without making "x" the operator and "A" and "B", in essence, the parameters.

Writing "(A . B)(x) == (B . A)(x)" or "A . B == B . A" would make the commutative part of the formula a bit more visible--not that it was really hidden. I just wasn't looking at it from the right perspective.

Posted Apr 20, 2012 0:29 UTC (Fri) by mmorrow (subscriber, #83845) [Link]

> I thought you were..

(I wasn't the author of the original comment.)

> Writing "(A . B)(x) == (B . A)(x)" or "A . B == B . A" would make the commutative part of the formula a bit more visible..

It definitely would have made it clearer.

> ..a general version of the commutative property, not a specialized version for function composition..

Ah, but actually the case where a binary operator is commutative over its entire domain is the special case (in the mathematical sense, blah).

It's just that in programming we don't often (explcitly) deal with non-commutative binary operators, and even less often with non-commutative operators which are commutative when restricted to a subset of their domain.

Here's a quick roughly-phrased example:

Consider a rubik's cube. Think of a "move" as a function which maps a cube configuration to another configuration. This is a non-commutative group with elements these cube-config-maps and binary operator function composition. Now, for any two moves f and g which don't "interfere" (e.g. rotate top, rotate bottom), (f . g) == (g . f).

Posted Apr 20, 2012 1:13 UTC (Fri) by mmorrow (subscriber, #83845) [Link]

Here's a better example:

The "elements" are C stmts thought of as mappings of memory configurations, and the binary operator is `;`. This is a monoid with identity element the empty C stmt.

Define,

modify(S) := the set of memory locations statement S *may* modify.

So now, `;` is commutative for every pair of statements S,T which *must not* (i.e. cannot under any possible dynamic execution path) modify one or more of the same memory locations.

(S ; T)===(T ; S) <==> modify(S)/\modify(T)==empty_set

(where "===" := equivalence wrt effect on memory)

Posted Apr 20, 2012 1:37 UTC (Fri) by mmorrow (subscriber, #83845) [Link]

Actually that's not quite correct, it's more like:

(S ; T)===(T ; S)
<==>
modify(S)/\modify(T)==empty_set
AND
AND

or something along these lines, but the idea is clear.

Posted Apr 20, 2012 8:19 UTC (Fri) by mpr22 (subscriber, #60784) [Link]

Programmers tell their programs to subtract, divide, and/or shift fairly frequently.