Boolean Expressions

In SML, Boolean values are denoted directly, meaning the value “true” is denoted true, and the value “false” is denoted false. The set of Boolean values is referred to as the type bool. We say: The value true is a value of type bool. By this we mean that true is an element of the type (i.e., set) bool.

Conditional Expressions

In programming languages, conditional expressions (and conditional statements) provide a very important mechanism for controlling the flow of execution in a program. In SML, a conditional expression has the form shown below.

if e1 then e2 else e3

 

In the conditional expression above (also known as an if-then-else expression), the words if, then, and else are keywords and e1, e2, e3 denote expressions.

In order for a conditional expression to be well-typed, the expression e1 must be of type bool, and the expressions e2 and e3 must have the same type. The expression e1 is referred to as the condition of the conditional expression. The expression e2 is referred to as the then-branch of the conditional expression, and the expression e3 is referred to as the else-branch of the conditional expression. A well-formed conditional expression like the one shown above is evaluated as follows.

  1. The expression e1 is reduced to its normal form. Since, e1 is of type bool, its normal form will be either true or false.
  2. Case A: e1 ⇒ true. In this case, the evalution of the conditional expression proceeds in the following manner.
    if e1 then e2 else e3 ⇒ if true then e2 else e3 ⇒ e2
  3. Case B: e1 ⇒ false. In this case, the evalution of the conditional expression proceeds in the following manner.
    if e1 then e2 else e3 ⇒ if false then e2 else e3 ⇒ e3

An important thing to notice about the evaluation of if e1 then e2 else e3 is that only either (1) e1 and e2 will be evaluated, or (2) e1 and e3 will be evaluated. In a single evaluation it will never be the case that e1, e2, and e3 will all (three) be evaluated. This kind of selective evaluation is known as short-circuiting. Though the syntax of conditional expressions may differ from one language to another, all mainstream programming languages short-circuit the evaluation of conditional-expressions in the manner described. To confirm that the evaluation of conditional expressions are indeed short-circuited, try evaluating the following conditional expressions.

  1. if true then 3 * 0 else 3 div 0
  2. if false then 3 div 0 else 3 * 0
  3. if true then 3 div 0 else 3 * 0

Note that the evaluation of the third expression demonstrates what happens when the computer tries to evaluate 3 div 0. While not a proof, the results of this experiment are consistent with statement that the evaluation of conditional expressions is short-circuited in SML.

Control Flow

An important aspect of conditional expressions is they provide a mechanism for controlling the flow of execution in a program. Consider the functiontwoBricks shown below whose formal parameter is a 3D point. The body of this function is a conditional expression that evaluates to a BLACK brick when the x value of the point it is applied to is even and a WHITE brick when x value is odd. Thus, in the body of the function twoBricks there are two different computational possibilities (or paths).

fun twoBricks (x,y,z) = if x mod 2 = 0 then BLACK 
                        else WHITE                   

The table below shows the results of three different calls to the function twoBricks

Expression    Evaluation Result   
twoBricks (0,0,0) BLACK
twoBricks (0,1,1) BLACK
twoBricks (1,0,0) WHITE

Conditional expressions can be combined in various ways to produce code through which a number of computational paths are possible. Care needs to be taken in order to avoid constructing code that is overly complex. In the code shown below the body of the function threeBricks consists of a nested conditional expression. Specifically, the then-branch of the larger (outermost) conditional expression is itself another (nested) conditional expression.

fun threeBricks (x,y,z) = 
    if x mod 2 = 0 then
        if x mod 4 = 0 then BLUE
        else LIGHTBLUE
    else RED                   

The table below shows the results of three different calls to the function threeBricks

Expression    Evaluation Result   
threeBricks (2,0,0) LIGHTBLUE
threeBricks (4,1,1) BLUE
twoBricks (1,0,0) RED

In the Bricklayer program below, the function threeBricks is passed as a parameter to the function traverseWithin. The function traverseWithin is a Level 5 Bricklayer function that accepts three arguments: two points that define a rectangular prism, and a function f that when applied to a point will return a brick. When called, traverseWithin will traverse (or visit) all the points in the given rectangular prism. To each point (x,y,z) visited, traverseWithin will place at that point, the (brick) result of the function call f(x,y,z).

In the example below, traverseWithin will traverse (in no particular order) over all the points in the set { (0,0,0), …, (8,0,8) }. A point (x,y,z) is processed by placing, in the virtual space, the brick returned from the function call threeBricks(x,y,z). Note that in the resulting artifact, it visually appears that the blue horizontal line falls underneath the red vertical line. How would the conditional expression in the function threeBricks need to be changed so that the red line appears to fall underneath the blue line?

open Level_5; 

fun threeBricks (x,y,z) = 
    if x mod 2 = 0 then
        if z mod 4 = 0 then BLUE
        else LIGHTBLUE
    else RED;

build (9,1,9);

traverseWithin (0,0,0) (8,0,8) threeBricks;

show "control flow";                      

level-5-threeBricks

Boolean Operators

In SML, there are three Boolean operators shown in the table below that we will consider to be primitive operators.

Operator    SML Symbol    Example
disjunction orelse true orelse false = false
conjunction andalso true andalso false = false
negation not not true = false

Technically speaking, andalso and orelse are derived forms. Essentially, this means that expressions involving these operators are a shorthand notation for other (computational equivalent) expressions. An initial part of executing an SML program involves a preprocessing stage where derived forms are transformed (i.e., translated) into their computationally equivalent counterparts. The rules for how expressions containing andalso and orelse operators are transformed are shown below.

Derived Form    Computationally Equivalent Expression   
e1 orelse e2 if e1 then true else e2
e1 andalso e2 if e1 then e2 else false

The not operator is simply a function that has been defined in SML.

Relational Operators

SML has four relational operators: (1) less than (<), (2) less than or equal to (<=), (3) greater than (>), and (4) greater than or equal to (>=). SML also has two equality-based operators: (1) equal to (=), and (6) not equal to (<>). Collectively the relational operators and equality-based operators are calledcomparison operators. The comparison operators can be used to compare integers. The equality-based operators can be used to compare aggregate values (e.g., tuples and lists) constructed from integers.

Expression    Result   
4 < 5 true
4 <> 5 true
(2,3) = (2,3) true
[3,4,5] = [3,4,5] true

Precedence and Associativity

The table below gives the precedence and associativity for Boolean, comparison, and integer operators. Note that the precedence of orelse and andalso are ~2 and ~1 respectively. This is in contrast to mathematics where the logical operators and and or have the same precedence. A good rule of thumb is the following.

When in doubt insert parenthesis to make explicit the order of evaluation desired.

 

In SML, function application has the highest precedence. Since not is nothing more than an SML defined function, its application has the highest precedence.

Operator    Precedence    Associativity
orelse ~2 left associative
andalso ~1 left associative
=, <>, <, >, <=, >= 4 left associative
+, – 6 left associative
*, div, mod 7 left associative
not highest left associative