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 a branching construct that will enable us to build more complex programs. Subsequent experiences will discuss constructs useful for repeating segments of code.

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 general flowchart representing a conditional is:

A flowchart representing the specific requirements from above is:

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. At the end of the consequent, a jump is executed to skip the alternative.

Going Deeper

A jump instruction is used to inform the CPU to go directly to another address, skipping any intervening instructions. A jump can move either forward or backward in the code. A jump may also be either unconditional, meaning that it will always be executed, or conditional, meaning that it will only be executed if certain conditions are met.

Conditions are most often based on flags. Refer to CPU and find the SR Register. It contains the status of a recent operation, such as whether or not the result is zero, negative, or if there was an overflow condition. Each of these conditions sets a flag, a single bit (usually within a series of similar bits) which has a specific meaning. Common flags include:

Name	Indicator	Function
Carry flag	C	Indicates that a carry (or borrow) was required during an operation
Negative (sign) flag	N	Indicates that the result of an operation was negative
Overflow flag	V	Indicates that an arithmetic overflow has occurred, i.e., a two's-complement binary number would not fit in the available width
Zero flag	Z	Indicates that the result of an operation was zero

The mnemonic for an unconditional jump is often jmp. Common conditional jumps include:

Mnemonic	Meaning	Flags Examined
je	Jump if equal	Z=1
jne	Jump if not equal	Z=0
jg	Jump if greater	N=0 AND Z=0
jge	Jump if greater or equal	N=0 OR Z=1
jl	Jump if lesser	N ≠ V
jle	Jump if lesser or equal	N ≠ V OR Z=1

Carefully study the following assembly language example:

        .global _start

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

test:
        # 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, jump conditionally (less-than or equal)
        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"

Observe

Observe, Ponder, and Journal: Section 2

1. Why is the first Jump instruction conditional? What determines whether the jump will be executed or not?
2. What is the purpose of the Jump instruction after the consequent?
3. Why is there no need for a corresponding Jump instruction after the alternative?

Swift

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

	Coming Soon
	Special cases: Consequent without alternative Chained alternatives

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

Exercises

Exercises

1.  J1151  Create a journal and answer all questions in this experience. Be sure to include all sections of the journal, properly formatted.
2. Using Draw.IO and following the instructions DrawIO Saving a File, create the below flowcharts. Be certain to label each flowchart using the correct exercise number. Place the text into a file named J1151.xml and be sure to push it to GitHub when done.
   1. Create a flowchart for making a peanut butter and jelly sandwich
   2. Create a flowchart for turning on a lamp in a room. Each day, the lamp should be turned on at sunset and off at sunrise.
   3. Create a flowchart for proceeding straight through a four-way intersection with stop signs at each corner.
   4. Create a flowchart for proceeding straight through a four-way intersection governed by a traffic light.
   5. Create a flowchart for making a left turn at a four-way intersection governed by a traffic light (without a left-turning arrow).
3.  M1151-10  Complete  Merlin Mission Manager  Mission M1151-10.