Syntax & Semantics: Relational Operators

[chharvey]

Tokenize the binary operators <, <=, !<, >, >=, !>, is, isnt.

Punctuator ::=
    | "<"
    | "<="
    | "!>"
    | ">"
    | ">="
    | "!>"
;

Keyword ::=
    // operator
        | "is"
        | "isnt"
;

Syntax:

ExpressionLessThan     ::= (ExpressionLessThan    ("<"  | "<=" | "!<"))?  ExpressionAdditive;
ExpressionGreaterThan  ::= (ExpressionGreaterThan (">"  | ">=" | "!>"))?  ExpressionAdditive;
ExpressionEquality     ::= (ExpressionEquality    ("is" | "isnt"     ))? (ExpressionLessThan | ExpressionGreaterThan);
-ExpressionConjunctive ::= (ExpressionConjunctive ("&&" | "!&"       ))?  ExpressionAdditive;
+ExpressionConjunctive ::= (ExpressionConjunctive ("&&" | "!&"       ))?  ExpressionEquality;

Note: ExpressionLessThan and ExpressionGreaterThan expressions can be syntactically chained, e.g., 3 < 4 < 5 and 9 > 8 > 7, though such expressions are not semantically meaningful yet. 3 < 4 < 5 is evaluated left to right, and is equivalent to (3 < 4) < 5. The first part of the expression is a boolean, and since booleans cannot be compared via <, it would be a type error. However, we want to make the syntax well-formed so that future versions of the language could produce a meaningful result: for example 3 < 4 < 5 could mean 3 < 4 && 4 < 5.

Note: Though ExpressionLessThan and ExpressionGreaterThan expressions separately may be chained, they may not be combined. 3 < 5 > 4 is not a well-formed expression and will result in a syntax error. (If you really wanted to do this you would need to write (3 < 5) > 4.) A future version may support generic function calls and a < B > (c) would be ambiguous with a<B>(c).

Semantics:

SemanticOperation[operator: LT | LE | GT | GE]
    ::= SemanticExpression[type: Integer | Float] SemanticExpression[type: Integer | Float];
SemanticOperation[operator: IS]
    ::= SemanticExpression[type: Object] SemanticExpression[type: Object];

Decorate(ExpressionLessThan ::= ExpressionAdditive) -> SemanticOperation
    := Decorate(ExpressionAdditive);
Decorate(ExpressionLessThan ::= ExpressionLessThan "<" ExpressionAdditive) -> SemanticOperation
    := (SemanticOperation[operator=LT]
        Decorate(ExpressionLessThan)
        Decorate(ExpressionAdditive)
    );
Decorate(ExpressionLessThan ::= ExpressionLessThan "<=" ExpressionAdditive) -> SemanticOperation
    := (SemanticOperation[operator=LE]
        Decorate(ExpressionLessThan)
        Decorate(ExpressionAdditive)
    );
Decorate(ExpressionLessThan ::= ExpressionLessThan "!<" ExpressionAdditive) -> SemanticOperation
    := (SemanticOperation[operator=NOT]
        (SemanticOperation[operator=LT]
            Decorate(ExpressionLessThan)
            Decorate(ExpressionAdditive)
        )
    );

Decorate(ExpressionGreaterThan ::= ExpressionAdditive) -> SemanticOperation
    := Decorate(ExpressionAdditive);
Decorate(ExpressionGreaterThan ::= ExpressionGreaterThan ">" ExpressionAdditive) -> SemanticOperation
    := (SemanticOperation[operator=GT]
        Decorate(ExpressionGreaterThan)
        Decorate(ExpressionAdditive)
    );
Decorate(ExpressionGreaterThan ::= ExpressionGreaterThan ">=" ExpressionAdditive) -> SemanticOperation
    := (SemanticOperation[operator=GE]
        Decorate(ExpressionGreaterThan)
        Decorate(ExpressionAdditive)
    );
Decorate(ExpressionGreaterThan ::= ExpressionGreaterThan "!>" ExpressionAdditive) -> SemanticOperation
    := (SemanticOperation[operator=NOT]
        (SemanticOperation[operator=GT]
            Decorate(ExpressionGreaterThan)
            Decorate(ExpressionAdditive)
        )
    );

Decorate(ExpressionEquality ::= ExpressionLessThan) -> SemanticOperation
    := Decorate(ExpressionLessThan);
Decorate(ExpressionEquality ::= ExpressionGreaterThan) -> SemanticOperation
    := Decorate(ExpressionGreaterThan);
Decorate(ExpressionEquality ::= ExpressionEquality "is" ExpressionLessThan) -> SemanticOperation
    := (SemanticOperation[operator=IS]
        Decorate(ExpressionEquality)
        Decorate(ExpressionLessThan)
    );
Decorate(ExpressionEquality ::= ExpressionEquality "is" ExpressionGreaterThan) -> SemanticOperation
    := (SemanticOperation[operator=IS]
        Decorate(ExpressionEquality)
        Decorate(ExpressionGreaterThan)
    );
Decorate(ExpressionEquality ::= ExpressionEquality "isnt" ExpressionLessThan) -> SemanticOperation
    := (SemanticOperation[operator=NOT]
        (SemanticOperation[operator=IS]
            Decorate(ExpressionEquality)
            Decorate(ExpressionLessThan)
        )
    );
Decorate(ExpressionEquality ::= ExpressionEquality "isnt" ExpressionGreaterThan) -> SemanticOperation
    := (SemanticOperation[operator=NOT]
        (SemanticOperation[operator=IS]
            Decorate(ExpressionEquality)
            Decorate(ExpressionGreaterThan)
        )
    );

Type TypeOf(SemanticOperation[operator: LT | LE | GT | GE | IS] expr) :=
    1. *Return:* `Boolean`.

The less than (<), greater than (>), less than or equal to (<=), and greater than or equal to (>=) operators compare number values in the traditional sense. The operators !< and !> are syntax sugar.

a !< b; % sugar for `!(a < b)` % in most cases, equivalent to `a >= b`
a !> b; % sugar for `!(a > b)` % in most cases, equivalent to `a <= b`

In numerical uses, !< is equivalent to >= and !> is equivalent to <=. However, this might not hold for future operator overloads. For instance, if the relational operators were overloaded to mean “subset” for sets, then a !< b (“a is not a strict subset of b”) does not necessarily mean that a >= b (“a is a superset of b”).

The identity operator is determines whether two operands are the same object. For null, boolean values, number values, and string values, this is the same as equality. For other future types, identity and equality might not necessarily be the same: objects that are considered equal might not be identical. Support for an equality operator == and an inequality operator != will be added in the future.

The operator isnt is the logical negation of is.

a isnt b; % sugar for `!(a is b)`

[chharvey]

This leads to a reduce-reduce conflict:

ExpressionLessThan     ::= (ExpressionLessThan    ("<"  | "<=" | "!<"))?  ExpressionAdditive;
ExpressionGreaterThan  ::= (ExpressionGreaterThan (">"  | ">=" | "!>"))?  ExpressionAdditive;
ExpressionEquality     ::= (ExpressionEquality    ("is" | "isnt"     ))? (ExpressionLessThan | ExpressionGreaterThan);

since an ExpressionAdditive can’t decide whether to reduce to an ExpressionLessThan or ExpressionGreaterThan. Update the grammar to combine all less-than and greater-than operators:

ExpressionComparative ::= (ExpressionComparative ("<" | ">" | "<=" | ">=" | "!<" | "!>"))? ExpressionAdditive;
ExpressionEquality    ::= (ExpressionEquality    ("is" | "isnt"))?                         ExpressionComparative;

Note that this will allow expressions such as a < B > (c), which is ambiguous with generic routine calls. Since routine calls aren’t until v0.7.0, let’s cross that bridge when we get there. Maybe require a trailing comma (a<B,>(c)) or maybe tokenize the symbol >( as a single punctuator.

-Decorate(ExpressionConjunctive ::= ExpressionAdditive) -> SemanticExpression
-   := Decorate(ExpressionAdditive);
+Decorate(ExpressionConjunctive ::= ExpressionEquality) -> SemanticExpression
+   := Decorate(ExpressionEquality);

-Decorate(ExpressionConjunctive ::= ExpressionConjunctive "&&" ExpressionAdditive) -> SemanticOperation
+Decorate(ExpressionConjunctive ::= ExpressionConjunctive "&&" ExpressionEquality) -> SemanticOperation
    := (SemanticOperation[operator=AND]
        Decorate(ExpressionConjunctive)
-       Decorate(ExpressionAdditive)
+       Decorate(ExpressionEquality)
    );

-Decorate(ExpressionConjunctive ::= ExpressionConjunctive "!&" ExpressionAdditive) -> SemanticOperation
+Decorate(ExpressionConjunctive ::= ExpressionConjunctive "!&" ExpressionEquality) -> SemanticOperation
    := (SemanticOperation[operator=NOT]
        (SemanticOperation[operator=AND]
            Decorate(ExpressionConjunctive)
-       Decorate(ExpressionAdditive)
+       Decorate(ExpressionEquality)
        )
    );

[chharvey]

Since is compares by identity, it should be the case that 0.0 is -0.0 produces false, since they are different floating-point values (even though they are mathematically equal).

The semantics of <= and >= need to be explicit:

a <= b; % produces the same result as `a == b || a < b`
a >= b; % produces the same result as `a == b || a > b`

which means adding the == operator for equality.

-ExpressionEquality ::= (ExpressionEquality ("is" | "isnt"              ))? ExpressionComparative;
+ExpressionEquality ::= (ExpressionEquality ("is" | "isnt" | "==" | "!="))? ExpressionComparative;

-SemanticOperation[operator: IS]
+SemanticOperation[operator: IS | EQ]
    ::= SemanticExpression[type: Object] SemanticExpression[type: Object];

+Decorate(ExpressionEquality ::= ExpressionEquality "==" ExpressionComparative) -> SemanticOperation
+   := (SemanticOperation[operator=EQ]
+       Decorate(ExpressionEquality)
+       Decorate(ExpressionComparative)
+   );
+Decorate(ExpressionEquality ::= ExpressionEquality "!=" ExpressionComparative) -> SemanticOperation
+   := (SemanticOperation[operator=NOT]
+       (SemanticOperation[operator=EQ]
+           Decorate(ExpressionEquality)
+           Decorate(ExpressionComparative)
+       )
+   );

-Type TypeOf(SemanticOperation[operator: LT | LE | GT | GE | IS] expr) :=
+Type TypeOf(SemanticOperation[operator: LT | LE | GT | GE | IS | EQ] expr) :=
    1. *Return:* `Boolean`.

The equality operator == determines whether two operands are considered “equal” by some definition, based on the type of the operands. For null, boolean values, and number values, it is drafted below. String equality is not yet defined, but will consist of comparing code units, one by one. For collections (such as arrays), it will consist of comparing equality of the collection’s items, one by one.

// (pseudo-prose)
Boolean Equal(Object a, Object b) :=
    1. If `TypeOf(a)` and `TypeOf(b)` are different, return `false`.
    2. If `TypeOf(a)` is `Null`, return `true`.
    3. If `TypeOf(a)` is `Boolean`:
        1. Return whether `a` and `b` are both `false` or both `true`.
    4. If `TypeOf(a)` is `Integer`, return whether `a` and `b` are identical.
    5. If `TypeOf(a)` is `Float`:
        1. If `a` and `b` are identical, return `true`.
        2. If `a` is `0.0` or `-0.0`, and `b` is `0.0` or `-0.0` return `true`.
        3. Return `false`.
    // 6. TODO: strings, tuples, arrays, records, functions, sets
    7. Return whether `a` and `b` are identical.

[chharvey]

This comment was deleted and replaced with #40.