De Morgan Law Optimization with Overloaded Operators

Question

Every programmer should know that:

( Morgan Laws)

In some cases, in order to optimize the program, it may happen that the compiler changes (!p && !q) to (!(p || q)) .

The two expressions are equivalent, and there is no difference in evaluating the first or second.
But in C ++, you can overload operators, and an overloaded operator may not always respect this property. Thus, transforming the code in this way will actually change the code.

Should the compiler use De Morgan's laws when ! , || and && overloaded?

Answer 1

Note that:

Built-in operators && and || perform a short circuit assessment (do not evaluate the second operand if the result is known after evaluating the first), but overloaded operators behave like normal function calls and always evaluate both operands .

... Since the short-circuited properties of the && operator and the operator || do not belong to overloads and because types with Boolean semantics are unusual, only two classes of the standard library overload these operators ...

Source: http://en.cppreference.com/w/cpp/language/operator_logical (emphasis mine)

So what:

If there is a user-written candidate with the same name and parameter types as the built-in function of the candidate operator, the built-in operator function is hidden and is not included in the set of candidate functions.

Source: n4431 13.6 Built-in Operators [over.built] (emphasis added)

To summarize: overloaded operators behave like normal user-written functions.

NO, the compiler will not replace a call to a user-defined function with a call to another user-defined function. Otherwise, it may potentially violate the “as if” rule.

Answer 2

I think you answered your question: no, the compiler cannot do this. Not only operators can be overloaded, some cannot even be defined. For example, you can define operator && and operator ! , and operator || not defined at all.

Note that there are many other laws that the compiler cannot follow. For example, he cannot change p||q to q||p , as well as x+y to y+x .

(All of the above apply to overloaded operators, as this asks a question.)

Answer 3

No, in this case the conversion will be invalid. Permission to convert !p && !q to !(p || q) implicit, as-if rule. The as-if rule allows any conversion, which, roughly speaking, cannot be observed using the correct program. When overloaded operators are used and detect a transformation, this automatically means that the conversion is no longer allowed.

Answer 4

Overloaded operators themselves are just syntactic sugar for function calls ; the compiler itself is not allowed to make any assumptions about properties that may or may not be performed for such calls. Optimizations that use the properties of a particular operator (for example, De Morgan for Boolean operators, commutativity for sums, distributivity for sums / products, integral division transforms in the corresponding multiplication, ...) can be used only when "real operators" are used .

Please note that some parts of the standard library may associate some specific semantic values ​​with overloaded operators - for example, std::sort by default expects operator< correspond to strict weak ordering between elements - but this refers to the course specified in the premises of each algorithm / container.

(by the way, overloading && and || should probably be avoided, since they lose their short-circuited properties during overloading, so their behavior becomes unexpected and therefore potentially dangerous)

Answer 5

You ask if the compiler can arbitrarily rewrite your program to make it impossible for you to write it.

Answer: of course not!

• If the laws of De Morgan apply, they may apply.
• If they do not, they cannot.

It's really that simple.

Answer 6

Not directly.

If p and q are expressions, so p does not have overloaded operators, a short circuit assessment is performed: the expression q will be evaluated only if p is false.

If p is of a non-primitive type, then there is no short circuit estimate, and an overloaded function can be anything - not even related to normal use.

The compiler will perform its optimizations in its own way. Perhaps this could lead to the definition of Morgan, but not at the level of substitution of the condition.

Answer 7

DeMorgan laws apply to the semantics of these operators. Overloading applies to syntax these operators. There is no guarantee that an overloaded operator implements the semantics that are necessary for the application of DeMorgan laws.

Answer 8

But in C ++, you can overload operators, and an overloaded operator may not always respect this property.

An overloaded operator is no longer an operator; it is a function call.

 class Boolean { bool value; .. Boolean operator||(const Boolean& b) { Boolean c; c.value = this->value || b.value; return c; } Boolean logical_or(const Boolean& b) { Boolean c; c.value = this->value || b.value; return c; } } 

So this line of code

 Boolean a (true); Boolean b (false); Boolean c = a || b; 

equivalent to this

 Boolean c = a.logical_or(b);