He gives reduce as an example of "purely functional programs have no side effects and are thus trivially parallelizable.", but reduce by definition is not trivially parallelizable.
(retract "he's wrong")
Only in really strongly typed languages like Agda can you make the associativity constraint /part of the type/ of the function, and thus statically checked by the compiler; but it's perfectly reasonable to make it part of the specification of the function's behavior that it expects its argument to be associative. (Or, slightly more generally, that the order of reduction is unspecified; in which case only an associative function will produce a totally deterministic result.)
On a related note, I would like to see a "perverse" compiler and library which exhibits random behavior when undefined behavior is specified by the language.