Booleans and Conditional Computation

Overview

In this chapter we will focus on another language, which instead of operating on integers, operates on booleans. We start by defining its grammar with formation rules, followed by a Rust enum representing its abstract syntax. After that, we naturally define how its terms evaluate to values. Finally, we will learn about lowering surface language to a lower, less human-readable language with fewer operations.

In the next chapter, we will merge the prefix arithmetic language and this boolean language.

Boolean Language

Our boolean language, denoted , has two literals true and false. In addition, we will initially only have one boolean operation: if-then-else (the boolean recursor). For example, the following is a term in the language:

The if-then-else operation might be familiar to some as the ternary conditional operator (? :) available in some programming languages.

Grammar of The Boolean Language

Together, true, false and if-then-else are expressed with the following formation rules:

The first two are “axioms” so we treat them as base rules and don’t bother drawing a line on top.

As an example, the term if true then false else true has the following formation tree:

AST in Rust

The type of abstract syntax tree for the boolean language can be written as the following enum in Rust

enum AST {
    True,
    False,
    Ite {
        cond: Box<AST>,
        if_true: Box<AST>,
        if_false: Box<AST>,
    }
}

Evaluation Rules

We will use for the set/type of booleans, i.e. the two-element set where denotes false and true.

The evaluation relation has the following shape: , where and . The base rules are straight-forward:

Let’s try to think about what the evaluation rules of if-then-else look like.

First, what are the possible values of an if-then-else expression? Clearly there are two options:

• The value of if evaluates to true.
• The value of if evaluates to false.

In addition, even though it’s mathematically irrelevant, we want to avoid unnecessarily evaluating the other branch.

Next, what are the premises in each option?

• If evaluates to true, we need for to evaluate to some value, e.g. .
• If evaluates to false, we need for to evaluate to some value, e.g. .

These two options can be defined nicely with two evaluation rules.

Alternative IfTrue Rule

0 / 3 points

How does evaluation change if instead of the IfTrue rule, we use the following rule?

Ignoring the Condition

0 / 3 points

How does evaluation change if we add the following rule (in addition to the existing rules)?

Evaluating Both Branches

0 / 3 points

How does evaluation change if instead of the IfFalse rule, we use the following rule?

Instances of IfTrue

0 / 2 points

How many different values can b₂ take in valid instances of the IfTrue rule?

Syntax Sugar

Syntax sugar is the term used for syntax which gets converted to a lower, less human readable syntax. For example lists in can be written as [1, 2, 3:Int] which is not converted to an AST node List(1, 2, 3) but rather to a nested Cons(1, Cons(2, Cons(3, Nil(Integer)))) structure.

The process of lowering (or desugaring) syntax sugar can take place between a high-level AST and a lower level AST. One of the primary reasons behind lowering syntax sugar comes the fact that evaluation is likely simpler to implement at the lower level.

Let’s add some more syntax and operators to :

We represent the binary operators in infix style (as opposed to prefix) as we don’t need to write a parser for them and it makes them more natural to read.

We would like to avoid having to define any extra semantics for these operators by desugaring the sugared syntax to the “core language” consisting only of true, false and if-then-else terms. After parsing an expression in , we can lower it to an AST using a translation function.

This is a nice way programming languages can add convenient features which don’t fundamentally alter the behavior of the language.

First, let’s define the SugaredAST in Rust:

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>),
}

Let’s denote the translate function with double square bracket notation

We want the unsugared fragment (True, False and Ite) of the sugared language to effectively “remain unchaged” during the desugaring.

Next, let’s start with how to desugar ! b. The definition of negation of a boolean is:

This definition has the mathematical structure of an if-then-else expression. Therefore it’s straight-forward to encode it in AST with an if-then-else:

Pulling Back Across The Sugar

Using this operation, we can simply pull back the evaluation function to get

Now all of the following terms evaluate to the values we expect.

In the next exercise, your task is to desugar And, Or, Xor into just True, False and Ite.