Skip to content

Latest commit

 

History

History
359 lines (268 loc) · 13.7 KB

p0680.md

File metadata and controls

359 lines (268 loc) · 13.7 KB
Raw

And, or, not

Pull request

Table of contents

Problem

Logical AND, OR, and NOT are important building blocks for working with Boolean values. Carbon should support them.

Background

Usage in existing languages

Most mainstream programming languages use one (or both) of two syntaxes for these operators:

  • &&, ||, and !. The && and || operators were first used by C to distinguish short-circuiting behavior from that of regular operators. They are now seen in C, C++, C#, Swift, Rust, Haskell, and many more languages. && and || invariably short-circuit.

  • and, or, and not. These are often used by languages with more emphasis on readability and scripting, such as Python, Pascal, Nim, SQL, and various variants of BASIC. In Python, the and and or operators short-circuit; in Pascal and Visual Basic, they do not, but variants of them do:

    • and then and or else in Pascal short-circuit.
    • AndAlso and OrElse in Visual Basic short-circuit.

    C++ recognizes and, or, and not as keywords and treats them as lexical synonyms for &&, ||, and !. C provides an <iso646.h> standard header that exposes and, or, and not as macros expanding to &&, ||, and !.

Perl, Ruby, and Raku permit both syntaxes, giving the punctuation forms higher precedence and the keyword forms lower precedence. Both forms short-circuit. Raku also provides andthen and orelse, but these differ from and and or in what value is produced on short-circuiting, not in whether they short-circuit.

Zig provides and, or, and !.

Known issues with punctuation operators

The use of && and || for short-circuiting logical operators is a common source of error due to the potential for confusion with the bitwise & and | operators. See:

We have anecdotal evidence that the ! operator is hard to see for some audiences in some contexts, particularly when adjacent to similar characters: parentheses, I, l, 1.

Proposal

Carbon will provide three operators to support logical operations on Boolean values.

  • and provides a short-circuiting logical AND operation.
  • or provides a short-circuiting logical OR operation.
  • not provides a logical NOT operation.

Note that these operators are valid alternative spellings in C++; PR #682 provides a demonstration of what this proposal would look like if applied to the C++ code in the Carbon project.

Details

and and or are infix binary operators. not is a prefix unary operator.

Precedence

and, or, and not have very low precedence. When an expression appearing as the condition of an if uses these operators unparenthesized, they are always the lowest precedence operators in that expression.

These operators permit any reasonable operator that might be used to form a boolean value as a subexpression. In particular, comparison operators such as < and == have higher precedence than all logical operators.

A not operator can be used within and and or, but and cannot be used directly within or without parentheses, nor the other way around.

For example:

if (n + m == 3 and not n < m) {

can be fully parenthesized as

if (((n + m) == 3) and (not (n < m))) {

and

if (cond1 == not cond2) {
// ...
if (cond1 and cond2 or cond3) {

are both errors, requiring parentheses.

Associativity

and and or are left-associative. A not expression cannot be the operand of another not expression -- not not b is an error without parentheses.

// OK
if (not a and not b and not c) { ... }
if (not (not a)) { ... }

// Error
if (not a or not b and not c) { ... }
if (not not a) { ... }

Conversions

The operand of and, or, or not is converted to a Boolean value in the same way as the condition of an if expression. In particular:

  • If we decide that certain values, such as pointers or integers, should not be usable as the condition of an if without an explicit comparison against null or zero, then those values will also not be usable as the operand of and, or, or not without an explicit comparison.
  • If an extension point is provided to determine how to branch on the truth of a value in an if (such as by supplying a conversion to a Boolean type), that extension point will also apply to and, or, and not.

Overloading

The logical operators and, or, and not are not overloadable. As noted above, any mechanism that allows types to customize how if treats them will also customize how and, or, and not treats them.

Rationale based on Carbon's goals

  • Code that is easy to read, understand, and write:

    • The choice of and and or improves readability by avoiding the potential for visual confusion between && and &.
    • The choice of not improves readability by avoiding the use of a small and easy-to-miss punctuation character for logical negation.
    • Having no precedence rule between and and or avoids readability problems with expressions involving both operators, by requiring the use of parentheses.
    • The use of a keyword rather than punctuation for these operators helps emphasize that they are not regular operators but instead have control-flow semantics.
    • Using the same precedence for not as for and and or allows conditions to quickly be visually scanned and for the overall structure and its nested conditions to be identified.

  • Interoperability with and migration from existing C++ code:

    • The use of the operators and, or, and not, which are keywords with the same meaning in C++, avoids problems with a Carbon keyword colliding with a valid C++ identifier and allows early adoption of the Carbon syntax in C++ codebases.
    • While these operators are overloadable in C++, && and || are nearly the least-overloaded operators, and ! is generally only overloaded as a roundabout way of converting to bool. There is no known need for Carbon code to call overloaded C++ operator&&, operator||, or operator!, nor for Carbon code to provide such operators to C++. We will need a mechanism for if, and, or, and not to invoke (possibly-explicit) operator bool defined in C++, but that's outside the scope of this proposal.

Alternatives considered

Use punctuation spelling for all three operators

We could follow the convention established by C and spell these operators as &&, ||, and !.

Advantage:

  • This would improve familiarity for people comfortable with this operator set.

Disadvantages:

  • The use of keywords rather than punctuation gives a hint that and and or are not merely performing a computation -- they also affect control flow.
  • The ! operator is known to be hard to see for some readers.
  • If we also support & and | operators, there is a known risk of confusion between && and & and between || and |.
  • If we want to change the precedence rules, using a different syntax can serve as a reminder that these operators do not behave like the &&, ||, and ! operators.
  • &&, ||, and ! are likely to be harder to type than and, or, and not on at least most English keyboard layouts, due to requiring the use of the Shift key and reaching outside the letter keys.

Precedence of AND versus OR

Most languages give their AND operator higher precedence than their OR operator:

if (a && b || c && d) { ... }
// ... means ...
if ((a && b) || (c && d)) { ... }

This makes sense when viewed the right way: && is the multiplication of Boolean algebra and || is the addition, and multiplication usually binds tighter than addition.

We could do the same. However, this precedence rule is not reliably known by a significant fraction of developers despite having been present across many languages for decades, leading to common recommendations to enable compiler warnings for the first form in the above example, suggesting to rewrite it as the second form. This therefore fails the test from proposal #555: when to add precedence edges.

Precedence of NOT

We could give the not operator high precedence, mirroring the behavior in C++. In this proposal, the not operator has the same precedence rules as and and or, which may be inconvenient for some uses. For example:

var x: Bool = cond1 == not cond2;

is invalid in this proposal and requires parentheses, and

var y: Bool = not cond1 == cond2;

is equivalent to

var y: Bool = cond1 != cond2;

which may not be what the developer intended.

However, giving not higher precedence would result in a more complex rule and would break the symmetry between and, or, and not.

Punctuation form of NOT

We could use the spelling ! for the NOT operator instead of not.

The syntax of the not operator may be harder to read than a ! operator for some uses. For example, when its operand is parenthesized, because it contains a nested and or or:

if (not (thing1 and thing2) or
    not (thing3 and thing4)) {

Also, the spelling of the != operator is harder to justify if there is no ! operator.

However:

  • Changing the syntax would break the symmetry between and, or, and not.
  • Python uses this set of keywords and has a != operator, and that doesn't appear to cause confusion in practice.
  • not may be easier to read than ! in some uses, and easier to pick out of surrounding context.
  • ! is being used to indicate early substitution in generics, so avoiding its use here may avoid overloading the same syntax for multiple purposes.
  • A function-like not (...) may better conform to reader expectations than a !(...) expression.

Two forms of NOT

We could combine the two previous alternatives, and introduce both a low-precedence not operator and a high-precedence ! operator.

This would allow us to provide both a convenient ! operator for use in subexpressions and a consistent not keyword that looks and behaves like and and or.

However, including both operators would either lead to one of the forms being unused or to the extra developer burden of style rules suggesting when to use each. Also, it may be surprising to provide a ! operator but not && and || operators.

Repeated NOT

We could permit the syntax not not x as an idiom for converting x to a Boolean type. However, we hope that a clearer syntax for that will be available, such as perhaps x as Bool. In the presence of such syntax, not not x would be an anti-pattern, and may indicate a bug due to an unintentionally repeated not operator. Per #555: when to add precedence edges, when in doubt, we omit the precedence rule and wait for real-world experience.

AND and OR produce the decisive value

We could make the AND and OR operator produce the (unconverted) value that determined the result, rather than producing a Boolean value. For example, given nullable pointers p and q, and assuming that we can test a pointer value for nonnullness with if (p), we could treat p or q as producing p if p is nonnull and q otherwise.

This is the approach taken by several scripting languages, notably Python, Perl, and Raku. It is also the approach taken by std::conjunction and std::disjunction in C++.

Advantages:

  • Provides a syntactic method to compute the first "truthy" or last "falsy" value in a list.

Disadvantages:

  • The resulting code may be harder to read and understand, especially when the value is passed onto a function call.
  • Requires all conditions in a chained conditional to have a common type, or the use of a fallback rule in the case where there is no common type.
  • When combined with type deduction, an unexpected type will often be deduced; for example, var x: auto = p and q; may deduce x as having pointer type instead of Boolean type.