W1151 Conditional and Flow Chart

From Coder Merlin
Confluence

Prerequisites[edit]

Introduction[edit]

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[edit]

   Sequential Assembly.png

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[edit]

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
Directional Arrow Indicates the direction of flow through the diagram, particularly when the flow is not in the traditional top-to-bottom order.
Terminal Indicates the beginning or end of a program or function.
Process 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:

Flowchart for Hello World.png

Conditional Execution[edit]

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[edit]

A general flowchart representing a conditional is:

   Conditional Flowchart.png

A flowchart representing the specific requirements from above is:

   Flowchart for Rivercruise with Meal.png

Note the new symbol in the flowchart:

Symbol Meaning
Decision 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.
ObserveIcon.png
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[edit]

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

   Conditional Assembly.png

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.

GoingDeeperIcon.png
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:

 1         .global _start
 2 
 3         .text
 4 _start:
 5         # assume we begin with the number 5
 6         mov     $5, %rax                   # move 5 into the register rax
 7 
 8 test:
 9         # we then test to see if the number is greater than 4
10         cmp     $4, %rax                   # subtract 4 from the contents of register rax
11 
12         # evaluate test condition, jump conditionally (less-than or equal)
13         jle      alternative
14 
15 consequent:
16         # write(1, messageConsequent, 10)
17         mov     $1, %rax                   # system call 1 is write
18         mov     $1, %rdi                   # file handle 1 is stdout
19         mov     $messageConsequent, %rsi   # address of string to output
20         mov     $10, %rdx                  # number of bytes
21         syscall                            # invoke operating system to do the write
22         jmp     afterAlternative
23 
24 alternative:
25         # write(1, messageAlternative, 11)
26         mov     $1, %rax                   # system call 1 is write
27         mov     $1, %rdi                   # file handle 1 is stdout
28         mov     $messageAlternative, %rsi  # address of string to output
29         mov     $11, %rdx                  # number of bytes
30         syscall                            # invoke operating system to do the write
31 
32 afterAlternative:
33         # exit(0)
34         mov     $60, %rax                  # system call 60 is exit
35         xor     %rdi, %rdi                 # we want return code 0
36         syscall                            # invoke operating system to exit
37 
38 messageConsequent:
39         .ascii  "Consequent"
40 messageAlternative:
41         .ascii  "Alternative"
ObserveIcon.png
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[edit]

let x = 5
if x > 4 {
    print("consequent")
} else {
    print("alternative")
}
ComingSoonIcon.png
Coming Soon
  • Special cases:
    • Consequent without alternative
    • Chained alternatives

Key Concepts[edit]

KeyConceptsIcon.png
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[edit]

ExercisesIcon.png
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

References[edit]