Iteration [WIP]

[aznricepuff]

Lesson: Iteration

Probably one of the most important abilities of any program is to carry out repetitive tasks over and over. This might seem silly, but without repetition we would be left with only the simplest of programs. Almost every programming algorithm (an algorithm is a set of purely mechanical instructions guaranteed to produce the correct result every time it is executed) ever written relies on repetition.

In JASS the most basic method of executing repetitive code is iteration.

A Model of Iteration

Iteration is the first (and in many ways the simpler) method of executing repetitive code in JASS. To put it simply, iteration is the execution of a block of code repeatedly while some condition (the loop condition) is true. Code that is iterated over is often said to be in a loop. A model of iteration might look something like this:

1. Enter loop.
2. If the loop condition is true then go to 3. Otherwise go to 4.
3. Execute code within the loop, then go back to 2.
4. Exit loop.

Graphically this can be represented as:

In the above image, circles link to squares of the same color (as shown by the arrows). So whenever we encounter a circle we jump to the place indicated by the square of the same color. The teal box represents of the section of code that checks if the loop condition is true. The yellow box represents the section of code that is iterated over, often called the loop body.

Iteration in JASS

JASS offers a single control structure for iteration: the loop/endloop block. Let's take a look at one:

function PrintOneToTen takes nothing returns nothing
    local integer i = 1
    loop
        exitwhen (i > 10)
        call BJDebugMsg(I2S(i))
        set i = i + 1
    endloop
    call BJDebugMsg("Done.")
endfunction

The above function prints out the numerals one through ten using iteration, then prints out "Done." Let's go through the function to see how it works step by step.

function PrintOneToTen takes nothing returns nothing
    local integer i = 1 // <==
    loop
        exitwhen (i > 10)
        call BJDebugMsg(I2S(i))
        set i = i + 1
        call BJDebugMsg("Done.")  
    endloop
endfunction

The marked line is called the initialization of the loop. Basically we are setting the local variable i to a value of 1.

function PrintOneToTen takes nothing returns nothing
    local integer i = 1
    loop // <==
        exitwhen (i > 10)
        call BJDebugMsg(I2S(i))
        set i = i + 1
    endloop
    call BJDebugMsg("Done.")
endfunction

The loop keyword denotes the start of a loop block (loop body).

function PrintOneToTen takes nothing returns nothing
    local integer i = 1
    loop
        exitwhen (i > 10) // <==
        call BJDebugMsg(I2S(i))
        set i = i + 1
    endloop
    call BJDebugMsg("Done.")
endfunction

The exitwhen statement is what JASS uses to check a loop condition. However, instead of continuing the iteration when some condition (the loop condition) is true, it breaks the iteration (exits the loop) if some condition is false. Therefore, instead of placing the loop condition in the exitwhen statement, we would need to place the negation of the loop condition in the statement.

function PrintOneToTen takes nothing returns nothing
    local integer i = 1
    loop
        exitwhen (i > 10)
        call BJDebugMsg(I2S(i)) // <==
        set i = i + 1
    endloop
    call BJDebugMsg("Done.")
endfunction

This line is really the meat of the loop. It prints out the number stored in the local variable i.

function PrintOneToTen takes nothing returns nothing
    local integer i = 1
    loop
        exitwhen (i > 10)
        call BJDebugMsg(I2S(i))
        set i = i + 1 // <==
    endloop
    call BJDebugMsg("Done.")
endfunction

This line increments the value stored in the local variable i up by one.

function PrintOneToTen takes nothing returns nothing
    local integer i = 1
    loop
        exitwhen (i > 10)
        call BJDebugMsg(I2S(i))
        set i = i + 1
    endloop // <==
    call BJDebugMsg("Done.")
endfunction

The endloop keyword marks the end of a loop block. When code execution within the loop block reaches the endloop keyword, it jumps back to the loop keyword and will continue to do so forever unless the execution exits the loop via an exitwhen statement.

function PrintOneToTen takes nothing returns nothing
    local integer i = 1
    loop
        exitwhen (i > 10)
        call BJDebugMsg(I2S(i))
        set i = i + 1
    endloop
    call BJDebugMsg("Done.") // <==
endfunction

This is the first line of code after the loop block. It is the first line of code to be executed when code execution exits the loop.

Building Iterative Code

Now that we've seen how iteration works in JASS, let's create an iterative function. We'll start off simple. Our function will calculate the sum of the squares of all integers from 0 to n, where n is some non-negative integer. In other words, it will calculate the value of:

0² + 1² + 2² + 3² + ... + n²

Before we even start an attempt to write code for this, let's think first about how we would do something like this without using programming. We would begin by taking 0 and squaring it. Then we would take 1 and square it and add it to the square of 0. Then we would take 2 and square it and add it to the sum of the square of 1 and the square of 0. And we would continue doing this for every integer until we got to n. Remember this description well because we will keep coming back to it when trying to figure out what our code should be.

Now we begin coding. We start off with just the function declaration:

function SumOfSquares takes integer n returns integer
endfunction

We already know we want to create a loop, so the first thing we need to do is to initialize the loop. What is an appropriate initialization? Looking back to our non-coding description of the task, we see that we repeatedly calculate the squares of integers. Well for a program to calculate the square of an integer it needs to know the value of said integer; in other words we need a local integer variable to keep track of which integer we are squaring. We will also need another local integer variable to keep track of the sum of the squares we have already calculated.

function SumOfSquares takes integer n returns integer
    local integer sum
    local integer i
endfunction

Our initialization is not done yet. We know that we need to calculate the squares of integers from 0 to some non-negative integer n. And no matter what, the first square we calculate is going to be 0 squared. So we need to initialize i to 0. We must also initialize sum to 0 because at this point, we haven't calculated any squares yet and the sum of nothing is simply 0.

function SumOfSquares takes integer n returns integer
    local integer sum = 0
    local integer i = 0
endfunction

Initialization is now finished. Now to add the loop body:

function SumOfSquares takes integer n returns integer
    local integer sum = 0
    local integer i = 0
    loop
    endloop
endfunction

Our model of iteration says that we need some condition such that when the condition is true, the loop continues to iterate and otherwise code execution exits the loop. Well, in our non-coding description, we said that we only repeatedly calculate the squares of integers if the integers are between 0 and n. So our condition for the continued execution of the loop is i >= 0 and i <= n. But remember that in JASS, loop conditions are dealt with using exitwhen statements, which take the negation of the condition as it would appear in our model. So what goes into our code is actually:

function SumOfSquares takes integer n returns integer
    local integer sum = 0
    local integer i = 0
    loop
        exitwhen (i < 0 or i > n)
    endloop
endfunction

Now to think about what goes in the meat of the loop body. Well remember what we did non-codewise was to take the square of an integer and add it to the sum of all the squares of the integers that came before it. So to do it in our code we need to add two things. Firstly we need another local variable to keep track of the sum. Secondly we add a line inside the loop body to calculate the square of an integer and add it to the sum:

function SumOfSquares takes integer n returns integer
    local integer sum = 0
    local integer i = 0
    loop
        exitwhen (i < 0 or i > n)
        set sum = sum + i * i
    endloop
endfunction

We are almost done with the loop. The last thing we need to do is to take into account the fact that once we are finished calculating the square of some integer and adding it to the sum, we must move on to the next greatest integer and repeat the process. Well our loop takes care of the repetition part since that's what a loop does. However, we must make sure to change i in such a way that every time the loop repeats, i is bumped up to the next greatest integer. We can achieve this simply by adding 1 to i at the very end of the loop body:

function SumOfSquares takes integer n returns integer
    local integer sum = 0
    local integer i = 0
    loop
        exitwhen (i < 0 or i > n)
        set sum = sum + i * i
        set i = i + 1
    endloop
endfunction

Now all that is left is to return the answer:

function SumOfSquares takes integer n returns integer
    local integer sum = 0
    local integer i = 0
    loop
        exitwhen (i < 0 or i > n)
        set sum = sum + i * i
        set i = i + 1
    endloop
    return sum
endfunction

There! We have created a function that returns the sum of the squares of all integers from 1 to some positive integer n. There is actually one last thing we can do. If we look closely at the code, we see that i can never be less than 1. We initialize it to 1 and then all we ever do to it is add 1. Therefore, we can clean up the exitwhen statement since it is pointless to check to see if i is less than 1 if it is always greater than or equal to 1.

So the following is our final function:

function SumOfSquares takes integer n returns integer
    local integer sum = 0
    local integer i = 0
    loop
        exitwhen (i > n)
        set sum = sum + i * i
        set i = i + 1
    endloop
    return sum
endfunction

Unconditionally Exiting a Loop

Unlike most languages, JASS does not provide a separate keyword for unconditionally exiting a loop (often called "breaking" the loop). However, we can use the following syntax to simulate an unconditional break:

    loop
        // some code ...
        exitwhen (true) // <==
        // some more code ...
    endloop

By using the boolean literal true we are guaranteeing that this exit condition is true under all circumstances. Therefore whenever code execution reaches this line, it will exit the loop.

Homework

Short Answer Problems

Give a one to two sentence answer to the following questions. Writing up code is not necessary unless you feel it helps to illustrate your answer.

1. What is the loop condition (not the exit condition) for the following loop?
   

       loop
           exitwhen (i > 100)
       endloop

2. How many iterations will the following loop go through? (A single iteration is defined as one complete execution of the entire loop body.)
   

       local integer i = 0
       loop
           exitwhen (i > 10)
           set i = i + 1
       endloop

3. What does the following function do?
   

   function Foo takes integer j, integer k returns integer
       // j and k are both positive
       local integer m = j
       loop
           exitwhen (ModuloInteger(m, k) == 0)
           set m = m + j
       endloop
       return m
   endfunction

Coding Problems

Write up JASS code for each problem that meets the given specifications.

1. Write an iterative function that prints out every pair of integer (x, y) coordinates that lies on or is contained within the square whose four vertices are (0,0), (0, 20), (20, 0), and (20, 20).
2. Write an iterative function that computes the factorial of a non-negative integer n (n!).
3. Write an iterative function that computes the product of two non-negative integers j and k. You may not use the multiplication operator (*).
4. Write an iterative function that computes the exponent a raised to the b power (a^b) for some integer a and some non-negative integer b. You may not use the Pow() function.

Challenge Problems

These are optional problems that you may try at your own discretion. They are often far more difficult than the other types of problems.

1. Write an iterative function that computes integer division between two non-negative integers j and k, where j is the dividend and k is the divisor (in other words j / k). Remember that integer division always truncates (rounds down) the quotient to the nearest integer. You may not use the division operator (/)
2. Suppose you are given the function function GetInteger takes integer i returns integer. The function takes in an integer parameter i from 0 to some non-negative number n and returns a unique arbitrary integer m such that the larger the value of i, the larger the value of m. In other words:
   
   GetInteger(0) < GetInteger(1) < GetInteger(2) < ... < GetInteger(n)
   
   Write an iterative function that takes some integer m and some non-negative integer n and finds the integer 0 <= i < n such that GetInteger(i) = m. If there is no such integer i, the function should return -1. For some extra challenge, implement your function so that it does not have to iterate over every i from 0 to n.
3. Write an iterative function that approximates the value of the mathematical constant e. The accuracy of your approximation is up to you, but you should be accurate to at least 2 or 3 decimal places. You may use your factorial function from Coding Problem 1. (Hint: use the MacLaurin series of e^x.)

 

[wyrmlord]

First, the small things. There's an extra [/code] tag at the end of your lesson and you have [n]exitwhen[/b] near the end of your SumOfSquares example. You have a

left near the beginning of the recursive section, but by the looks of things, you'll probably change it once you find a suitable picture.

Personally, I've never used recursion at all in JASS and I'd suggest either not teaching it, or saving it until much later since we're likely dealing with new JASS users and iteration is already a large topic in itself.

For the second challenge problem in the iterative section, I'd suggest giving enough information for the problem to be solved without having to look at external sources. To be honest, I have no idea what a MacLaurin series is nor how factorial is used to find the value of e since it hasn't been talked about much yet in my math classes. While some people may recognize what this means, I'm willing to bet that a good amount of people reading these lessons will not know what you are referring to.

That's all I have for now.

 

[aznricepuff]

Yea, I've made a sum total of one recursive function in about 5 years of coding in JASS, so I agree that it's almost a non-issue in JASS. I guess I'll split iteration from recursion and post the recursion stuff in a new thread. We can figure out what to do with that later.

As for the maclaurin stuff, it's a challenge problem, so they don't have to do it. If they've never seen calculus (or e for that matter) before in their lives, then they can skip it. The problem is just there for those who might be interested in a little challenge. Maybe I'll add one (or two) more challenge problems that don't require such a high level of mathematics background to round things out a bit.

 

[PurplePoot]

The MacLaurin series for e^x is (eww, transparent background on a brown background site... open it in a new window if you want to be able to read it):

 

[aznricepuff]

If I highlight it, I can just barely read it (the fact that I know what it's supposed to say may have helped).

Anyways...updated. Got rid of the recursion stuff and made some other changes.