Programming Language Foundations

Conditional Arithmetic

---

Introduction

This chapter merges the prefix arithmetic language and the boolean language into one. Merging them is not entirely trivial, we need to work out for example what parts can we keep the same, what do we need to change, and what do we need to add.

Let’s start with what we know.

The AST of the arithmetic language is encoded as the following enum in Rust

pub enum AST {
    Num(i32),
    Add(Box<AST>, Box<AST>),
    Sub(Box<AST>, Box<AST>),
    Mul(Box<AST>, Box<AST>),
    Neg(Box<AST>),
    Div(Box<AST>, Box<AST>),
}

Likewise, the AST of booleans is as follows

enum AST {
    True,
    False,
    Ite {
        cond: Box<AST>,
        if_true: Box<AST>,
        if_false: Box<AST>,
    },
    Not(Box<AST>),
    And(Box<AST>, Box<AST>),
    Or(Box<AST>, Box<AST>),
    Xor(Box<AST>, Box<AST>),
}

Our goal is to combine these and create a language which has both arithmetic and boolean operations.

At first, it may seem like a good approch to give distinct names for these types (like ArithAST and BoolAST) and create a sum type ArithAST + BoolAST, however the resulting language is extremely limited. For example the term if true then 1 else 2 is clearly not in the language.

Another approach could be to make the types generic, and this is sometimes done to make the language constructs more extensible. This approach is perfectly valid approach to the problem.

Instead of going the generic route, we will write another AST which combines all of the features under one enum.

pub enum AST {
    Num(i32),
    Add(Box<AST>, Box<AST>),
    Sub(Box<AST>, Box<AST>),
    Mul(Box<AST>, Box<AST>),
    Neg(Box<AST>),
    Div(Box<AST>, Box<AST>),
    True,
    False,
    Ite {
        cond: Box<AST>,
        if_true: Box<AST>,
        if_false: Box<AST>,
    },
    Not(Box<AST>),
    And(Box<AST>, Box<AST>),
    Or(Box<AST>, Box<AST>),
    Xor(Box<AST>, Box<AST>),
}

Next, the type of values contains both integers and booleans as well as an error which can be either a “value error” or a type mismatch.

pub enum Error {
    /// A runtime error caused by values that were outside their legal range for the operator
    ValueError(String),
    /// A type mismatch between operands
    TypeMismatch(String),
}

pub enum Value {
    Int(i32),
    Bool(bool),
    Err(Error),
}

A type mismatch occurs when we try to operate on incompatible values, e.g. when trying to compare an integer with a boolean.

Loading Exercise...

Grammar of onditional Arithmetic

We denote the language of conditional arithmetic with the letter and include all the language from prefix arithmetic and the boolean language . To make the language more interesting, we add the usual integer comparison operators. Their grammar is as follows:

The rest of the operators, like !=, <= and >= will be added a bit later.

Evaluation Rules

We inherit the evaluation rules from the prefix arithmetic and the boolean language to . As the Value enum has become more complex, we need to take this into account in multiple places. First, in the Add rule, which adds the values :

We define addition between different Value as follows:

In the definition, if either of the summands is an error value, the result is an error. Also, in the mathematical definition we are hiding the implementation detail for producing a ValueError when adding the i32 values would overflow. We could express it as follows

For all if then

How to check if an arithmetic operation is within legal range in Rust is left as an exercise. Hint: checked methods.

Unlike the Add rule which didn’t need to be changed directly, the if-then-else rules need to be fixed to avoid evaluation from getting stuck. As a reminder, here are the old IfTrue and IfFalse rules:

We changed to true and to false to avoid confusion between integers and booleans.

The rules currently don’t address the situation if the condition evaluates to an error. In that situation, we want to propagate the error, just like how is done in addition between values. Let’s add an IfErr rule to the mix.

Let’s not forget to also “raise” an error if the condition is an integer.

Comparison Operator Evaluation Rules

Next, let’s define the semantics of the new == operator. As our values are split across integers, booleans and errors, we need to define comparison functions between values first. The equality comparison has the type , and is defined with the following equations:

In the definition, you should read the mathematical comparison and as an operation that returns a boolean.

With this operation on values, we can define the semantics of the == operator in one evaluation rule:

Loading Exercise...

Syntax Sugar for Conditional Arithmetic

As in the previous chapter, we would like to extend the language without having to extend its semantics. The core AST is all of the arithmetic and core boolean language, but only has the comparison operators ==, < and >. The sugared AST on the other hand extends the core AST with the !, and, or, xor, !=, <=, >= operators.

The desugaring function has the signature

The shared fragment behaves in the usual way

Here’s an example of how to define desugaring for <=

Rather than figuring out a new way to represent <= in the core AST, we take good use of the sugared language and construct a new sugared term which has the desired behavior. Of course one has to be careful not to make a cyclic definition, as that would lead to infinite recursion when desugaring.

Loading Exercise...

Loading Exercise...