Contents  Implementing  a Stack  Relocation  of Execution  Incorporating  the Stack  Program Flow  Demonstration  Source code  Printable version  Discuss this article The Series  An Introduction  Data Manipulation  Dynamic Loading  The Stack and  Program Flow

Demonstration

For a final demonstration of what we can now do, we will write a script that calculates the factorial of a particular number of our choosing. I chose to compute a factorial since it is something most readers should be familiar with. I will show how an iterative factorial would be performed as a function in C++, and then show how it can be broken down to be expressed as a script in our bytecode.

Iterative Factorial in C++:

int factorial (unsigned int input)
{
    // initialize
    int counter = input;
    int result = 1;

    // iterative loop
    while (counter > 1)
    {
        result *= counter;
        --counter;
    }

    // output
    return result;
}

We can begin deconstruction by analyzing the number of variables we will need to track, and in this case it is two (counter and result). The parameter input can be simulated as a constant supplied at the very beginning of our script. We will use index 0 as the counter, and index 1 as the result:

// initialize
push_const Input  // the actual value here is mutable
assign 0
push_const 1
assign 1

Handling the final output is also an easy section to deconstruct:

// output
push_var 1
output
end

The tricky part now comes in while flattening out the iterative loop. However, all we need to do is use the pattern described earlier for simulating a while loop:

A:
// evaluate condition
jump_if_false B
// do something
jump A
B:

The condition to be evaluated is simply a comparison between counter and the value 1:

// counter > 1
push_var 0
push_const 1
greater

And the action we are taking within the loop (do something) is multiplying result by counter, assigning the product to result, and then decrementing counter:

// result *= counter;
push_var 1
push_var 0
multiply
assign 1

// --counter;
push_var 0
push_const 1
subtract
assign 0

Now we put all of these pieces together, to get this:

push_const Input  // the actual value here is mutable
assign 0
push_const 1
assign 1
A:
push_var 0
push_const 1
greater
jump_if_false B
push_var 1
push_var 0
multiply
assign 1
push_var 0
push_const 1
subtract
assign 0
jump A
B:
push_var 1
output
end

The result is 20 instructions (not counting the labels of course). To finalize the process, we replace A and B by the proper offsets in our list. A corresponds to the 5th instruction, and B corresponds to the 18th (remember not to count A: as an instruction). Using 0 to N-1 index convention, that gives the 5th instruction an offset of 4, and the 18th an offset of 17.

A script that outputs the factorial of 4:

push_const 4
assign 0
push_const 1
assign 1
push_var 0
push_const 1
greater
jump_if_false 17
push_var 1
push_var 0
multiply
assign 1
push_var 0
push_const 1
subtract
assign 0
jump 4
push_var 1
output
end

Interesting Results

If you play around with the script's initial input value, you'll come to realize something... It only outputs the correct value for an input of 5 or less! What happened? The reason for this is our stack contains elements of type char, which implies a range of -128 to 127. The factorial of 5 is 120, just barely making the cut. So what if we want to find the factorial of 7? We only have to make a small change.

Behold the power of templates:

class Execution
{
. . .
private:
    ScopeStack<int> _stack; // initially of type ScopeStack<char>
    . . .
};

The factorial of 7 now comes out to be 5040, as it should be.

Conclusion

In my opinion, these have most interesting concepts developed in our low-level implementation so far. Although it is obviously tedious work, scripts can now be written to express many of the simple higher-level concepts we have always taken for granted. I leave the expression of some other high-level constructs (such as functions) as exercises for the reader until next time. The tools for expressing simple functions are here.

Check out the downloadable source for certain small changes in the test program we built last time in order to allow for our new instructions. One change was made to the parser to allow for underscores to be scanned as part of an opcode name. Other changes were made, but due to their trivial nature, they don't change the way the program behaves, and aren't really worth mentioning.

Please give me a piece of your mind in the forum discussion, or by email: glr9940@rit.edu