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 that 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 first reviews sequential flow and then discusses a branching construct that enables 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:

CoderMerlin™ Code Explorer: W0000 (1) 🟢

Assembly

C

C++

Java

Python

Swift

.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!"

Hide Compilation Output Sync  

Broadcast  

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 it represents the general use 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, especially 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 that 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 2 hours downriver from the Point—a park where the three rivers meet) 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 one cruise, in accordance with the schedule, offers a meal, the captain of the boat will stop at the Point for an hour when 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 can also be either unconditional, meaning that it will always be executed, or conditional, meaning that it will be executed only 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 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) that has a specific meaning. Common flags include the following:

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 the following:

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:

CoderMerlin™ Code Explorer: W0000 (2) 🟢

Assembly

C

C++

Java

Python

Swift

.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"

Hide Compilation Output Sync  

Broadcast  

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

CoderMerlin™ Code Explorer: W0000 (3) 🟢

Assembly

C

C++

Java

Python

Swift

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

Hide Compilation Output Sync  

Broadcast  

	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 the following:
  • 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 on 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 skip certain instructions altogether or execute the same instructions multiple times. Whether such branching occurs is determined by 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 when done, be sure to push it to GitHub.
   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.