W1151 Conditional and Flow Chart

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Confluence

Prerequisites

• W1022 Computer Architecture
• W1041 Assembly Language

Introduction

Until now, the programs which we have observed and written exhibited sequential flow. That is, they had a single entry point and a single exit point. Instruction execution began at the entry point, instructions were executed sequentially, and then the program execution completed. While this type of flow is useful in some simple cases in the general case the flow will be more complex.

This experience will first review sequential flow and then discuss several constructs that enable us to build more complex programs.

Sequential Execution

In the example above, the program execution begins at address 0x8020 and completes at address 0x8026. All instructions are executed sequentially.

Let's examine a Hello, World! program in assembly language:

        .global _start

        .text
_start:
        # write(1, messageA, 6)
        mov     $1, %rax                # system call 1 is write
        mov     $1, %rdi                # file handle 1 is stdout
        mov     $messageA, %rsi         # address of string to output
        mov     $6, %rdx                # number of bytes
        syscall                         # invoke operating system to do the write

        # write(1, messageB, 6)
        mov     $1, %rax                # system call 1 is write
        mov     $1, %rdi                # file handle 1 is stdout
        mov     $messageB, %rsi         # address of string to output
        mov     $6, %rdx                # number of bytes
        syscall                         # invoke operating system to do the write

        # exit(0)
        mov     $60, %rax               # system call 60 is exit
        xor     %rdi, %rdi              # we want return code 0
        syscall                         # invoke operating system to exit

messageA:
        .ascii  "Hello "
messageB:
        .ascii  "World!"

Flowcharts

A flowchart is a type of diagram that enables us to visualize the flow of execution through a program. As such, flowcharts representing an entire program generally have a single entry point, a single exit point, and one or more processes. (In this case the word process is not the same as an operating system process, but represents the general usage of the word, i.e. "do something".) Throughout this experience, we'll introduce several symbols that are typically used in flowcharts.

Symbol	Meaning
	Indicates the direction of flow through the diagram, particularly when the flow is not in the traditional top-to-bottom order.
	Indicates the beginning or end of a program or function.
	Indicates an ordered series of logically grouped operations.

With these symbols in mind, let's take a look at a flowchart for the Hello, World program above:

Conditional Execution

Conditional execution is required when we need to make a choice regarding one or more alternatives. Observe the image at the top of this page which shows the confluence of the Allegheny and Monongahela rivers, forming the Ohio River. Now consider the Coder Merlin Riverboat Cruise Line schedule that runs between Arthur's Cafe (about two hours downriver from the Point) to Lancelot's Inn (about an hour upriver along the Allegheny):

Departure Time	Price	Meal Included	Cruise Duration
09:00	$49.99	✕	3 hours
11:00	$49.99	✕	3 hours
13:00	$69.99	✓	4 hours
15:00	$49.99	✕	3 hours
17:00	$69.99	✓	4 hours
19:00	$79.99	✓	4 hours

If a particular cruise, in accordance with the schedule, offers a meal, the captain of the boat will stop at the Point (a park located where the three rivers meet) for an hour during which time the meal is served.

Flowchart

A flowchart representing the above requirements follows:

Note the new symbol in the flowchart:

Symbol	Meaning
	Indicates that a branch in the flow occurs, most often based on a Boolean condition. Thus, there are most often two branches, usually labeled "Yes" and "No".

Such a branch is formally termed a conditional.

Conditionals consist of three distinct parts:

• A Boolean test. The Boolean expression is evaluated yielding either a true or false result.
• If the result of the Boolean test is true, execution proceeds with the consequent.
• If the result of the Boolean test is false, execution proceeds with the alternative.

Observe

Observe, Ponder, and Journal: Section 1

1. How does branching enable significantly more complex program behavior?
2. Why do you think the term consequent is used to refer to the statements that are executed when the Boolean test evaluates to true?

Assembly Language

Let's consider how the above construct is implemented in assembly language:

The condition, the Boolean test is evaluated. If the test evaluates to false, a jump is executed to the alternative, otherwise execution continues with the consequent. If the test evaluates to true, execution proceeds to the consequent. At the end of the consequent, a jump is executed to skip the alternative.

Carefully study the following assembly language example:

        .global _start

        .text
_start:
condition:
        # assume we begin with the number 5
        mov     $5, %rax                   # move 5 into the register rax

        # we then test to see if the number is greater than 4
        cmp     $4, %rax                   # subtract 4 from the contents of register rax

        # evaluate test condition
        jle      alternative

consequent:
        # write(1, messageConsequent, 10)
        mov     $1, %rax                   # system call 1 is write
        mov     $1, %rdi                   # file handle 1 is stdout
        mov     $messageConsequent, %rsi   # address of string to output
        mov     $10, %rdx                  # number of bytes
        syscall                            # invoke operating system to do the write
        jmp     afterAlternative

alternative:
        # write(1, messageAlternative, 11)
        mov     $1, %rax                   # system call 1 is write
        mov     $1, %rdi                   # file handle 1 is stdout
        mov     $messageAlternative, %rsi  # address of string to output
        mov     $11, %rdx                  # number of bytes
        syscall                            # invoke operating system to do the write

afterAlternative:
        # exit(0)
        mov     $60, %rax                  # system call 60 is exit
        xor     %rdi, %rdi                 # we want return code 0
        syscall                            # invoke operating system to exit

messageConsequent:
        .ascii  "Consequent"
messageAlternative:
        .ascii  "Alternative"

Swift

let x = 5
if x > 4 {
    print("consequent")
} else {
    print("alternative")
}

Key Concepts

Key Concepts

• A flowchart is a type of diagram that enables us to visualize the flow of execution through a program. Common symbols include:
  • An arrow indicating the direction of flow through the diagram
  • An oval indicating a terminal (either entry or exit) often labeled "START" or "END"
  • A rectangle indicating an ordered series of logically grouped operations
  • A rhombus indicating a decision, most often based upon a Boolean condition
• A program (or subprocess) exhibiting Sequential Execution means that execution begins at a single entry point, all instructions are executed sequentially, and then the program (or subprocess) exits through a single exit point
• A program (or subprocess) exhibiting Non-sequential Execution means that execution may, either skipping certain instructions altogether or executing the same instructions multiple times. Whether or not such branching occurs is determined based on runtime conditions.
• A conditional is a type of branching instruction with three distinct parts:
  • A Boolean Test
  • If the evaluation of the Boolean test is true, the consequent is executed, otherwise
  • if the evaluation of the Boolean test is false, the alternative is executed