Syntax & Semantics: Boolean Operators

[chharvey]

Lexing, parsing, and semantic analyzing of boolean operators.

Unary Operators

Tokenize the unary operators !, ?.

Punctuator ::=
    | "!"
    | "?"
;

Syntax:

ExpressionUnarySymbol
-   ::= ExpressionUnit | (            "+" | "-") ExpressionUnarySymbol;
+   ::= ExpressionUnit | ("!" | "?" | "+" | "-") ExpressionUnarySymbol;

Semantics:

SemanticOperation[operator: NOT]
    ::= SemanticExpression[type: Unknown];
SemanticOperation[operator: EMPTY]
    ::= SemanticExpression[type: Unknown];

Decorate(ExpressionUnarySymbol ::= "!" ExpressionUnarySymbol) -> SemanticOperation
    := (SemanticOperation[operator=NOT]
        Decorate(ExpressionUnarySymbol)
    );
Decorate(ExpressionUnarySymbol ::= "?" ExpressionUnarySymbol) -> SemanticOperation
    := (SemanticOperation[operator=EMPTY]
        Decorate(ExpressionUnarySymbol)
    );

Type TypeOf(SemanticOperation[operator: NOT | EMPTY] expr) :=
    1. *Return:* `Boolean`.

The “logical value” of a value is the boolean value that closely corresponds to the value. A value is said to be “falsy” if its “logical value” is false. Otherwise the value is said to be “truthy”.

Currently, the only “falsy” values are null and false. Any other value, including true, all numbers (including zeros: 0, 0.0. and -0.0), and all strings (including the empty string: ''), are “truthy”.

The unary operator ! logically negates the “logical value” of the operand. If the value is “falsy”, true is produced; otherwise false is produced.

The emptiness operator ? determines whether a value is considered “empty”. A value is “empty” if it’s “falsy”, if it’s a zero numeric value (0, 0.0. and -0.0), or if it’s an empty string. In future versions its semantics will be expanded to collections (such as arrays and sets, etc.).

Binary Operators

Tokenize the binary operators &&, !&, ||, !|.

Punctuator ::=
    | "&&"
    | "!&"
    | "||"
    | "!|"
;

Syntax:

ExpressionConjunctive ::= (ExpressionConjunctive ("&&" | "!&"))? ExpressionAdditive;
ExpressionDisjunctive ::= (ExpressionDisjunctive ("||" | "!|"))? ExpressionConjunctive;

Expression ::=
-   | ExpressionAdditive
+   | ExpressionDisjunctive
    | ExpressionConditional
;

Semantics:

SemanticOperation[operator: AND]
    ::= SemanticExpression[type=Unknown] SemanticExpression[type=Unknown];
SemanticOperation[operator: OR]
    ::= SemanticExpression[type=Unknown] SemanticExpression[type=Unknown];

Decorate(ExpressionConjunctive ::= ExpressionAdditive) -> SemanticOperation
    := Decorate(ExpressionAdditive);
Decorate(ExpressionConjunctive ::= ExpressionConjunctive "&&" ExpressionAdditive) -> SemanticOperation
    := (SemanticOperation[operator=AND]
        Decorate(ExpressionConjunctive)
        Decorate(ExpressionAdditive)
    );
Decorate(ExpressionConjunctive ::= ExpressionConjunctive "!&" ExpressionAdditive) -> SemanticOperation
    := (SemanticOperation[operator=NOT]
        (SemanticOperation[operator=AND]
            Decorate(ExpressionConjunctive)
            Decorate(ExpressionAdditive)
        )
    );
Decorate(ExpressionDisjunctive ::= ExpressionConjunctive) -> SemanticOperation
    := Decorate(ExpressionConjunctive);
Decorate(ExpressionDisjunctive ::= ExpressionDisjunctive "||" ExpressionConjunctive) -> SemanticOperation
    := (SemanticOperation[operator=OR]
        Decorate(ExpressionDisjunctive)
        Decorate(ExpressionConjunctive)
    );
Decorate(ExpressionDisjunctive ::= ExpressionDisjunctive "!|" ExpressionConjunctive) -> SemanticOperation
    := (SemanticOperation[operator=NOT]
        (SemanticOperation[operator=OR]
            Decorate(ExpressionDisjunctive)
            Decorate(ExpressionConjunctive)
        )
    );

Type TypeOf(SemanticOperation[operator: AND] expr) :=
    1. *Assert:* `expr.children.count` is 2.
    2. *Let* `t0` be `TypeOf(expr.children.0)`.
    3. *If* `t0` is `Null`:
        1. *Return:* `t0`.
    // 4. *If* `t0` is `ToType(false)`:
    //  1. *Return:* `t0`.
    5. *Let* `t1` be `TypeOf(expr.children.1)`.
    // 6. *If* `t0` is a type union containing `Null`, `ToType(false)`, or `Boolean`:
    //  1. *Note:* The left-hand operand is either “falsy” or “truthy”;
    //      if “falsy”, then it will be produced;
    //      if “truthy”, then the right-hand operand will be produced.
    //  2. *Return:* `TypeUnion(FalsifyType(t0), t1)`.
    // 7. *Note:* The left-hand operand is definitely “truthy”, thus
    //  the right-hand operand will definitely be produced.
    // 8. *Return:* `t1`.
    9. *Return:* `TypeUnion(t0, t1)`.
Type TypeOf(SemanticOperation[operator: OR] expr) :=
    1. *Assert:* `expr.children.count` is 2.
    2. *Let* `t0` be `TypeOf(expr.children.0)`.
    3. *Let* `t1` be `TypeOf(expr.children.1)`.
    4. *If* `t0` is `Null`:
        1. *Return:* `t1`.
    // 5. *If* `t0` is `ToType(false)`:
    //  1. *Return:* `t1`.
    // 6. *If* `t0` is a type union containing `Null`, `ToType(false)`, or `Boolean`:
    //  1. *Note:* The left-hand operand is either “falsy” or “truthy”;
    //      if “falsy”, then the right-hand operand will be produced;
    //      if “truthy”, then it will be produced.
    //  2. *Return:* `TypeUnion(TruthifyType(t0), t1)`.
    // 7. *Note:* The left-hand operand is definitely “truthy”, thus
    //  the left-hand operand will definitely be produced.
    // 8. *Return:* `t0`.
    9. *Return:* `TypeUnion(t0, t1)`.

The logical conjunction operator && (”and”) produces the left-hand operand if it is “falsy”; otherwise it produces the right-hand operand. The logical disjunction operator || (“or”) produces the left-hand operand if it is “truthy”; otherwise it produces the right-hand operand.

The “and” and “or” operators short-circuit, in that evaluation of the right-hand operand does not take place if it does not need to. If the left-hand operand of an && operation is “falsy”, then that operand is produced and the right-hand operand is not evaluated. Similarly, if the left-hand operand of an || operation is “truthy”, then that operand is produced and the right-hand operand is not evaluated. Short-circuiting can speed up runtime computation if the “simpler” expression is on the left.

Logical conjunction and disjunction are associative, which means the following groups of expressions produce the same result:

%% “and” is associative:
p && q && r;
(p && q) && r;
p && (q && r);

%% “or” is associative:
p || q || r;
(p || q) || r;
p || (q || r);

The operators !& (logical alternative denial, “nand”) and !| (logical joint denial, “nor”) are the logical negations of their counterparts; in fact they are syntax sugars.

a !& b; % sugar for `!(a && b)`
a !| b; % sugar for `!(a || b)`