PHP: a fractal of bad design (fuzzy notepad) [LWN.net]

PHP: a fractal of bad design (fuzzy notepad)

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)

PHP: a fractal of bad design (fuzzy notepad)

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 ;)

PHP: a fractal of bad design (fuzzy notepad)

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

PHP: a fractal of bad design (fuzzy notepad)

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.

PHP: a fractal of bad design (fuzzy notepad)

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).

PHP: a fractal of bad design (fuzzy notepad)

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)

PHP: a fractal of bad design (fuzzy notepad)

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
read(S)/\modify(T)==empty_set
AND
read(T)/\modify(S)==empty_set

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

PHP: a fractal of bad design (fuzzy notepad)

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.