Programming Language Design

Boolean Expression Language

---

Here, we look into a language for boolean computation — focusing on if true then true else false, and a variant with nested if statements possibly with spaces if true then if false then true else false else false.

Grammar

We can specify its grammar in a similar manner as with arithmetic expressions.

AST

The abstract syntax tree for boolean terms would have a way to create new booleans () and a way to destructure them ().

In the constructor, we use a mathematical “record notation” similar to Gleam records to indicate named fields.

AST as Formation Rules

Formation Rules

The suffix “-F” refers to a formation rule.

E.g. the term has the following formation tree:

Evaluation Rules

Let’s call the mathematical type for booleans, which has the two elements (false) and (true), simply (or ).

The evaluation relation now looks like , where and .

The idea behind the last two rules is to make our rule lazy/short-circuiting meaning that it does not compute the value of the branch that was not taken. The naïve version would look like this:

Here, we use a mathematical if-then-else construction which works exactly the same as in programming, but here and for some type .

Syntax Sugar for Lowering

Here’s a concrete example of how syntax sugar can be used to make a language more convenient for programmers.

After parsing into a a , we can do a desugaring translation into the original AST by turning the operators into if-then-elses. This would mean we don’t have to change the dynamics of the language. This is a nice way programming languages can add convenient features which don’t fundamentally alter the behavior of the language.

Let’s express the translate function using double square bracket notation: . As always, we can do case analysis on the argument of type :

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

Or, using the evaluation relation symbol:

Loading Exercise...