8.5: Looping

Last updated
Save as PDF

Page ID: 83032

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Loops are central to most algorithms, and hence play an important part in programming. When teaching looping, it seems that most students either tend towards or a taught a view of loops that focuses on how loops work, the reasoning about them. I find this is not really a fruitful approach to the subject, as simply some, if not most, students have a very difficult time recognizing that a loop counter variable takes on a different value each time through a for loop. This is why when teaching an introduction to programming class, the author would often emphasize the program plans to be implemented, and allow the students to develop their own model of how this worked.

This book will not try to explain how loops work, but rather introduce loops as a conical structure, just as the structure and not the logic of if statements was covered in the previous section. The program plans that then use loops will be implemented by expanding the loop structure, or more appropriately plan merging, where different types of plans are combined to create larger program plans.

All looping structures in this textbook will have the following structure:

# initialize first element 
startLoopLabel: 
    # check if loop is complete, if yes, branch to endLoopLabel 
    
    # loop block 
    
    # get next element
    # branch back to startLoopLabel 
endLoopLabel

This structure will be shown by construction to fit the major loop constructs, sentinel control loops and counter control loops, thus showing that for and while loops are both adequately addressed with this structure. In addition, by delaying the implementation of the loop block, the loop can be addressed as a complete unit, removing the nagging problems where parts of the loop, like branching back to startLoopLabel, is forgotten and omitted. Finally, by delaying the implementation of the loop block, the degree of complexity when implementing a program can be greatly reduced, making programs easier to implement, maintain, and use. This will be illustrated using a Bubble Sort at the end of the chapter.

The next two sections will show how to implement a sentinel control loop and a counter control loop. The two sections after that will show how to do plan merging by creating a program to query a user to calculate a summation until a sentinel value is entered.

8.5.1 Sentinel Control Loop

The definition of a sentinel is a guard, so the concept of a sentinel control loop is a loop with a guard statement that controls whether or not the loop is executed. The major use of sentinel control loops is to process input until some condition (a sentinel value) is met. For example, a sentinel control loop could be used to process user input until the user enters a specific value, for example -1. The following pseudo code fragment uses a while statement to implement a sentinel control loop which prompts for an integer and prints that integer back until the user enters a -1.

int i = prompt("Enter an integer, or -1 to exit") 
while (i != -1) 
{
    print("You entered " + i); 
    i = prompt("Enter an integer, or -1 to exit"); 
}

The following defines the steps involved in translating a sentinel control loop from pseudo code into assembly.

1. Initialize the loop by setting the sentinel to be checked before entering the loop. For the loop in this program, this requires a number of statements to one prompting and read user input.

2. Create a label for the start of the loop. This is so that at the end of the loop the program control can branch back to the start of the loop.

3. Create a label for the end of the loop. This is so the loop can branch out when the sentinel returns false.

4. Put the check to check the sentinel to see if the loop should be exited.

5. Set the sentinel to be checked as the penultimate statement(s) in the code block for the loop, and then unconditionally branch back to the start of the loop. This completes the loop structure, and you should have code that appears similar to the following:

.text 
.global main 

main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    MOV r0, #-0x32 
    
    # initialize by prompting user, answer in r4 
    LDR r0, =prompt 
    BL printf 
    LDR r0, =input 
    LDR r1, =num1 
    BL scanf
    LDR r1, =num1 
    LDR r4, [r1, 0]
    
StartSentinelLoop: 
    MOV r0, #-1 
    CMP r4, r1 
    BEQ EndSentinelLoop 
        
        # Loop Block 
        
        # Get next value 
        LDR r0, =prompt 
        BL printf 
        LDR r0, =input 
        LDR r1, =num1 
        BL scanf 
        LDR r1, =num1 
        
        B StartSentinelLoop

EndSentinelLoop: 
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr 
# End main

.data 
    prompt: .asciz "Please enter a number (-1 to end) \n" 
    output: .asciz "You entered %d\n" 
    input: .asciz "%d" 
    num: .word 0

6. The structure needed for the sentinel control loop is now in place. The logic to be executed in the code block can be included and any other code that is needed to complete the program. The final result of this program follows.

.text 
.global main 

main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    MOV r0, #-0x32 
    
    # initialize by prompting user, answer in r4 
    LDR r0, =prompt 
    BL printf 
    LDR r0, =input 
    LDR r1, =num 
    BL scanf 
    LDR r1, =num
    LDR r4, [r1, #0]

StartSentinelLoop: 
    MOV r0, #-1 
    CMP r4, r0 
    BEQ EndSentinelLoop
    
        # Loop Block 
        LDR r0, =output 
        MOV r1, r4 
        BL printf 
        
        # Get next value 
        LDR r0, =prompt 
        BL printf 
        LDR r0, =input 
        LDR r1, =num 
        BL scanf 
        LDR r1, =num 
        LDR r4, [r1, #0] 
        
        B StartSentinelLoop
        
EndSentinelLoop: 
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr 
# End main

.data 
    prompt: .asciz "Please enter a number (-1 to end) \n" 
    output: .asciz "You entered %d\n" 
    input: .asciz "%d" 
    num: .word 0

8.5.2 Counter control loop

A counter controlled loop is a loop which is intended to be executed some number of times. These are normally associated with a for loop in most HLLs. An example is the following pseudo code for loop which sums the values from 0 to (n-1).

n = prompt("enter the value to calculate the sum up to: ") 
total = 0; # Initialize the total variable for sum 

for (i = 0; i < n; i++) 
{ 
    total = total + i 
} 
print("Total = " + total);

The for statement itself has 3 parts. The first is the initialization that occurs before the loop is executed (“i=0”). The second is the condition for continuing to enter the loop (“i < size”). The final condition specifies how to get the next value, here the counter is incremented (“i++”, or add 1 to i). These 3 parts of a for loop map exactly into the loop structure covered earlier and are translated to this structure as follows.

Implement the initialization step to initialize the counter and the ending condition variables.
Place a startLoopLabel and an endLoopLabel in the program.
Implement the check to enter the loop block or stop the loop when the condition is met.
Add the code at the end of the loop to increment the counter and branch back to the start of the loop.

When you have completed these steps, the basic structure of the counter control loop has been implemented, and your code should look similar to the following:

.text 
    MOV r0, #0 
    MOV r5, #0 
    
    StartCountingLoop: 
        CMP r0, r4 
        BGE EndCountingLoop 
        
        # Loop Block 
        
        # Get next value 
        ADD r0, r0, #1 
        
        B StartCountingLoop 
    EndCountingLoop:

5. Implement the code block for the for statement. Implement any other code necessary to complete the program. The final assembly code for this program should look similar to the following.

.text 
.global main 

main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0]
    # Prompt for loop limit, store in r4 
    LDR r0, =prompt 
    BL printf 
    LDR r0, =input 
    LDR r1, =num 
    BL scanf 
    LDR r1, =num 
    LDR r4, [r1, #0] 
    
    # initialize the loop, 
    # r0 - counter 
    # r4 - loop limit 
    # r5 - sum 
    
    MOV r0, #0 
    MOV r5, #0
    
    StartCountingLoop: 
    CMP r4, r0 
    BLE EndCountingLoop
        
        # Loop Block 
        ADD r5, r5, r0
        
        # Get next value 
        ADD r0, r0, #1
        
        B StartCountingLoop
    EndCountingLoop:
    
    LDR r0, =output 
    MOV r1, r5 
    BL printf
    
    MOV r0, #0 
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr 
# End main

.data 
    prompt: .asciz "Please enter the loop limit to sum \n" 
    output: .asciz "The summation from 1 to n is %d\n" 
    input: .asciz "%d" 
    num: .word 0

8.5.3 Nested Code Blocks

It is common in most algorithms to have nested code blocks. A simple example would be a program which calculates the sum of all values from 0 to n, where the user enters values for n until a -1 if entered. In addition, there is a constraint on the input that only positive values of n be considered, and any negative values of n will produce an error.

This program consists of: a sentinel control loop, to get the user input; an if statement, to check that the input is greater than 0; and a counter control loop. The if statement is nested inside of the sentinel control block, and the counter loop is nested inside of the if-else statement. Now the importance of being able to structure this program using pseudo code, and to translate the pseudo code into assembly, becomes important.

The pseudo code for this algorithm follows. This pseudo code can be implemented in any HLL if the reader wants to assure themselves that it works, but it is fairly straight forward and should be easy to understand.

int n = prompt("Enter a value for the summation n, -1 to stop"); 
while (n != -1) 
{ 
    if (n < -1) 
    { 
        print("Negative input is invalid"); 
    } 
    else 
    { 
        int total = 0 
        for (int i = 0; i < n; i++) 
        { 
            total = total + i; 
        } 
        print("The summation is " + total); 
    } 
    n = prompt("Enter a value for the summation n, -1 to stop"); 
}

The program to implement this pseudo code is much larger and more complex. Implementing the program without first producing the pseudo code and translating it to assembly, even for a relatively simple algorithm such as this, is difficult and often yields unfavorable results. Unless the reader has a strong understanding of structured programming, the first step for implementing any program should be to implement it in structured code, either as pseudo code or in a HLL.

Translation of this pseudo code into assembly should following the structure of the program, as is illustrated below.

1. Begin by implementing the outer most block, the sentinel control block. Your code should look similar to the following:

.text 
.global main 

main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    # initialize by prompting user, answer in r4 
    LDR r0, =prompt 
    BL printf 
    LDR r0, =input 
    LDR r1, =num 
    BL scanf 
    LDR r1, =num 
    LDR r4, [r1, #0] 
    
    StartSentinelLoop: 
        MOV r0, #-1 
        CMP r4, r0 
        BEQ EndSentinelLoop 
        
        # Loop Block 
        
        # Get next value 
        LDR r0, =prompt 
        BL printf 
        LDR r0, =input 
        LDR r1, =num 
        BL scanf 
        LDR r1, =num 
        LDR r4, [r1, #0] 
        
        B StartSentinelLoop      
    EndSentinelLoop:

.data 
    prompt: .asciz "Please enter the loop limit to sum (-1 to end) \n" 
    output: .asciz "The summation from 1 to n is %d\n" 
    input: .asciz "%d"
    num: .word 0

2. The code block in the sentinel loop in the above fragment is now replaced by the if-else statement to check for valid input. The if-else block should just be the structure, and the code blocks should just be comments for now. Do not fill them in with the logic. When completed, your code should look similar to the following:

.text 
.global main 

main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    # initialize by prompting user, answer in r4 
    LDR r0, =prompt 
    BL printf 
    LDR r0, =input 
    LDR r1, =num 
    BL scanf 
    LDR r1, =num 
    LDR r4, [r1, #0] 
    
    StartSentinelLoop: 
        MOV r0, #-1 
        CMP r4, r0 
        BEQ EndSentinelLoop 
        
        # Input Check 
        MOV r0, #0 
        CMP r4, r0 
        BLE ElseInvalid 
            # If block 
            
            B EndInputCheck 
        
        ElseInvalid: 
            # Else block 
        
        EndInputCheck: 
        
        # Get next value 
        LDR r0, =prompt 
        BL printf 
        LDR r0, =input 
        LDR r1, =num 
        BL scanf 
        LDR r1, =num 
        LDR r4, [r1, #0]
        
        B StartSentinelLoop
    EndSentinelLoop:
    
.data 
    prompt: .asciz "Please enter the loop limit to sum \n" 
    badInput: .asciz "Your input value must be > 0 \n" 
    output: .asciz "The summation from 1 to n is %d\n" 
    input: .asciz "%d" 
    num: .word 0

3. The if block in the above code fragment is replaced by the summation loop from the previous program, and the else block is replaced by an error message about the value being invalid. This results in the following complete program. While this program is long, it is still fairly easy to follow the logic.

.text 
.global main 

main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    # initialize by prompting user, answer in r4 
    LDR r0, =prompt 
    BL printf 
    LDR r0, =input 
    LDR r1, =num 
    BL scanf 
    LDR r1, =num 
    LDR r4, [r1, #0] 
    
    StartSentinelLoop: 
        MOV r0, #-1 
        CMP r4, r0 
        BEQ EndSentinelLoop 
        
        # Input Check 
        MOV r0, #0 
        CMP r4, r0 
        BLE ElseInvalid 
            # summation loop 
            # initialize the loop, 
            # r0 - counter 
            # r4 - loop limit 
            # r5 - sum
            MOV r0, #0 
            MOV r5, #0 
            StartCountingLoop: 
            CMP r4, r0 
            BLE EndCountingLoop
                
                # Loop Block 
                ADD r5, r5, r0 
                
                # Get next value 
                ADD r0, r0, #1 
                
                B StartCountingLoop
            EndCountingLoop: 
            
            LDR r0, =output 
            MOV r1, r5 
            BL printf 
            
            B EndInputCheck
        ElseInvalid:
            # Print badInput message 
            LDR r0, =badInput 
            BL printf
            
        EndInputCheck: 
        
        # Get next value 
        LDR r0, =prompt 
        BL printf 
        LDR r0, =input 
        LDR r1, =num 
        BL scanf 
        LDR r1, =num 
        LDR r4, [r1, #0] 
        
        B StartSentinelLoop
    EndSentinelLoop: 
    
    MOV r0, #0 
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr
# End main

.data 
    prompt: .asciz "Please enter the loop limit to sum \n" 
    badInput: .asciz "Your input value must be > 0 \n"
    output: .asciz "The summation from 1 to n is %d\n" 
    input: .asciz "%d" 
    num: .word 0