Creating a Scripting System in C++ Part IV: The Stack and Program Flow

Premise

This article will introduce some new concepts that will allow us eventually to model higher-level languages with simple bytecode instructions. The variable data associated with scripts will become part of a stack, which will enhance the higher level behavior we can achieve with a handful of opcodes, and allow us to evaluate complex mathematical expressions with relative ease. With these new facilities added, it will also be possible for our scripts to have controlled program flow, including patterns for if-else and loops, as well as script-based functions.


The Reason for a Stack

A stack is a natural representation for many types of systems involving states and procedural calculation. One such use as mentioned is in evaluating expressions that involve more than a single operation, since such expressions can be broken into parts and handled step by step.

Consider a simple arithmetic expression:

x + y * p

Knowing simple rules for the ordering of operations, we can create a procedure for evaluating such an expression:

multiply y by p
add the result with x

Place this expression in the context of variable assignment, and you will begin to see how it relates to programming:

i = x + y * p

multiply y by p
add the result with x
assign the final result as the value of i

Notice that the procedure for evaluating such an expression mentions something that is only implicitly present in the expression itself. The procedure uses a term "result" which is understood to mean the result from the previous partial evaluation. It's almost an automatic assumption that we set aside the results of these sub-evaluations for use in further evaluations. What a stack will do for us is allow us to make this natural assumption. Being a LIFO (last in first out) data structure, we can push values onto it, pop them off to perform an operation, push the result back on, and so on until the parent evaluation is completed. By following a consistent set of evaluation rules, we can ensure that the stack will manage these "results" without us having to keep track of them.


Implementing a Stack

One of the first things that come to mind when thinking about stack implementations is that simple containers that could be used are already implemented as part of the standard library. They certainly are. However there will be certain features we need that they do not provide on their own.

We will start with a simple stack that uses a vector for its implementation:

template <class T>
class ScopeStack
{
public:
    ScopeStack() {}
    ScopeStack(size_t reserveSize)
        { _stack.reserve(reserveSize); }

    // todo: scope interface

    // element interface
    void Push(const T& element) { _stack.push_back(element); }
    void Pop()  { assert(!_stack.empty()); _stack.pop_back(); }

    // accessors
    const T& Top() const { assert(!_stack.empty()); return _stack.back(); }
    T& Top() { assert(!_stack.empty()); return _stack.back(); }
    const T& Get(size_t index) const { assert((index)<_stack.size());
                                       return _stack[index]; }
    T& Get(size_t index) { assert((index)<_stack.size()); return _stack[index]; }
    const T& operator[](size_t index) const { return Get(index); }
    T& operator[](size_t index) { return Get(index); }

    // properties
    size_t Size() const { return _stack.size(); }

private:
    std::vector<T>  _stack;
};

The stack can optionally be instantiated with memory reserved, and has an interface for pushing and popping individual elements. Random access, and access to the top of the stack are available, as is the size of the stack. On top of all this, assertions will guard against access that would fall out-of-bounds while debugging.

This should seem pretty straightforward, except for the name. But the reason for this name will become evident once we start dealing with chunks of variable data that are members of the same "scope" within a script.


Relocation of Execution

In order to accommodate for the things we would like to achieve regarding program flow and data accessing opcodes, we are going to want to move execution-specific implementation over to the appropriately named Execution class.

At the moment, the execution-specific code lies directly in the virtual machine. Instead, we would like the execution to take place as a member function of the Execution class, and have the virtual machine call to Execute redirect the execution to the proper Execution's execution. Say that ten times fast. If that sentence was as hard to follow as it was to type, the code will explain.

This is what we would like to have happen:

void VirtualMachine::Execute(size_t scriptId)
{
    _execution.Execute(SelectScript(scriptId)); // select our script by ID
}

The first step is to move the script and instruction pointers over to the Execution class. Simple enough. Next we will need to make a change to the SelectScript() utility:

ScriptRef SelectScript(size_t index) const  // set current script by id
{
    assert(index < _scriptList.size());  // make sure the id is valid
    return &_scriptList[index];
}

Instead of implicitly updating the pointers to the script and instructions (which it no longer possesses), it now simply returns the proper script pointer so that it may be passed to an Execution. It will also guard against improper script ids from being accepted through assertion.

Now we will need to create the Execution class's Execute() similar to that of VirtualMachine's before being changed:

void VirtualMachine::Execution::Execute(ScriptRef scriptPtr)
{
    _scriptPtr = scriptPtr;
    SetDataSize(_scriptPtr->VarCount());    // initialize variable data
    _instrPtr = _scriptPtr->InstrPtr();     // initialize root pointer
    _instrEnd = _scriptPtr->End();          // initialize end marker
    _instr = _instrPtr; // set our iterator to the beginning
    while (_instr < _instrEnd)  // ensure pointer stays in-bounds
    {
        switch(_instr->Code())
        {
        // message functionality
        case op_talk:
            std::cout << "I am talking." << std::endl;
            ++_instr;   // iterate
            break;
        case op_print:
            std::cout << _instr->Data() << std::endl;    // print data
            ++_instr;   // iterate
            break;
        // other functionality
    . . .
        // end
        case op_end:
            _instr = _instrEnd;  // discontinue the loop
            break;
        }
    }
}

Some changes have been made to how the loop is terminated after some re-evaluation. It will be safer this way once we bring in some new opcodes. To allow for this change, we add an additional accessor to the Script class to obtain a pointer to the end of its instruction list, and an end pointer to the Execution class.

This is all there is to it since the cast should be implicit:

// in the Script class
const Instruction* End() const      { return _instrList.end(); }

With all the said changes in place the loading example should still execute properly.


Incorporating the Stack

What we would like is to be able to replace the data vector we currently have in the Execution class with our new stack:

class Execution
{
public:
    . . . Interface . . .
private:
    ScopeStack<char>    _stack;
    ScriptRef           _scriptPtr; // executing script
    InstrRef            _instrPtr;  // root instruction
    InstrRef            _instrEnd;  // end of instruction list
    InstrRef            _instr;     // current instruction
};

Doing so will break some other parts of our implementation, unfortunately. The variable manipulation opcode handlers may need rewriting (if they are still desired), the execution's accessors have to be updated, and the function for exposing variable states will have to be changed entirely. Another function that will have to change is SetDataSize(). SetDataSize() and state exposure will need to wait until we finish implementing our custom stack.

The accessors are a simple change:

// data access
void SetVar(size_t i, char val) { _stack[i] = val; }
char GetVar(size_t i) const     { return _stack[i]; }

Before we can advance, we will have to begin implementing the scoping part of our stack. First will be a function to initialize what is essentially the outer-most scope. It's a simple resize:

void SetInitialScope(size_t scopeSize)
{
    // add guards to make sure this only happens once at the start
    _stack.resize(scopeSize);
}

Execution's SetDataSize() can now call this method:

void SetDataSize(size_t varCount)   { _stack.SetInitialScope(varCount); }

Now we would like to be able to create a group of variables on the stack that can be removed in the same group as well. This functionality will serve us well once we begin implementing a higher-level language with "scope" considerations. To do this, we will have to keep track of the starting positions of these scopes. I refer to these as indices in the implementation. Because we will need to store an additional index for every scope we push onto the stack, we will need to have some mechanism for storing these dynamically. The simple approach I will be taking will include an additional vector to store these indices. The index for the current scope will also be stored, and referred to as the stack base. Implementations for accessing variables from the current scope will then use the current index to find the right place on the actual data vector.

It will look something like this:

ScopeStack() : _stackBase(0)    {}
// scope interface
void SetInitialScope(size_t scopeSize)
{
    // initial scope should only be set once
    assert(_stack.empty() && _indices.empty());
    _stack.resize(scopeSize);
}        
void PushScope(size_t scopeSize)
{
    _indices.push_back(_stackBase);         // store the current index
    _stackBase = _stack.size();             // get new index
    _stack.resize(_stackBase+scopeSize);    // accomodate new scope data
}
void PopScope()
{
    assert(!_indices.empty());      // don't try to pop a non-existent scope
    _stack.resize(_stackBase);      // shrink back to the end of the former scope
    _stackBase = _indices.back();   // grab the base index for the former scope
    _indices.pop_back();            // take that index off the index stack
}
. . .
private:
    std::vector<T>      _stack;
    std::vector<size_t> _indices;
    size_t              _stackBase;

You might consider storing actual pointers to these stack positions instead of an actual offset into the vector, thinking you could be more efficient with such an approach. However there is the messiness involved in reallocation of the _stack in the event that its capacity is exceeded. The pointers would be invalidated. This is why I chose to store offsets as indices instead of pointers/iterators.

These accessors should now be updated accordingly. Note the change in index calculation:

const T& Get(size_t index) const
    { assert((_stackBase+index)<_stack.size()); return _stack[_stackBase+index]; }
T& Get(size_t index)
    { assert((_stackBase+index)<_stack.size()); return _stack[_stackBase+index]; }

Some new properties could be accessible as well:

size_t ScopeDepth() const
    { return _indices.size(); }
size_t GetScopeIndex(size_t depth) const
    { assert(depth<_indices.size()); return _indices[depth]; }

New accessors for getting an element indexed from a particular depth should be included. These do the same as the normal Get(), except they don't use the current stack depth as their starting point:

const T& GetAtDepth(size_t index, size_t depth) const
    { assert((GetScopeIndex(depth)+index)<_stack.size());
      return _stack[GetScopeIndex(depth)+index]; }
T& GetAtDepth(size_t index, size_t depth)
    { assert((GetScopeIndex(depth)+index)<_stack.size());
      return _stack[GetScopeIndex(depth)+index]; }

As I said earlier, the function to expose variable state now needs to be rewritten. This function will go through every element on the stack, while keeping track of the current stack depth, and output the value under its appropriate scope heading. It will be a member of the Execution class, and will take an ostream reference as a parameter to allow for flexible output options:

void VirtualMachine::Execution::ExposeStackState(ostream& out) const
{
    size_t numScopes = _stack.ScopeDepth();
    size_t stackSize = _stack.Size();
    size_t index, label, curDepth = 0, curEnd = 0;
    // for the entire stack
    for (index = 0, label = 0; index < stackSize; ++index, ++label)
    {
        if (index == curEnd)    // for every new scope in the stack
        {
            label = 0;
            out << "Scope Depth: " << curDepth << endl; // output the scope depth
            if (curDepth < numScopes)
            {
                curEnd = _stack.GetScopeIndex(curDepth);    // get end of this scope
                ++curDepth; // advance to next scope depth
            }
            else
                curEnd = 0;
        }
        // output each value
        out << "    " << label << ": " << static_cast<int>(_stack[index]) << endl;
    }
}

The virtual machine can now relay a call to this new function to show us the variable state through the console:

void ShowVariableState() const    { _execution.ExposeStackState(std::cout); }

And with that, the formerly written loading code should now work again with the new implementations.


A New Set of Instructions

To keep things tidy, I will be scrapping the old instructions from the provided source. Many of them would have found themselves redundant anyway. Now, here are some new instructions that will make use of the stack, each with a brief description of how they should work.

op_output:	pops top of the stack and outputs the value
op_push_const:	pushes a new value onto the stack
op_push_var:	pushes a variable's value onto the stack (variables residing lower in the stack)
op_assign:	pops the top of the stack and assigns it to a chosen position (lower in the stack)
op_add:	pops the top of the stack and adds it to the new stack top
op_subtract:	pops the top of the stack and subtracts itself from the new stack top
op_multiply:	pops the top and multiplies the new top by the popped value
op_divide:	pops the top and divides the new top by the popped value

The first three of these instructions will require an additional value. For the first instruction, the data value determines the value pushed onto the stack. For the next two, the data determines the index of the variable referenced either for having its value pushed onto the stack in the former case, or being assigned a value as in the latter.

A conceptual example of flat representation of an expression:

Expression:

x = x + 1

Flat Representation (our instructions):

push_var x
push_const 1
add
assign x

Note that 'x' is used as a placeholder for a particular variable index, which would correspond to the conceptual 'x' written in the higher-level expression. During a compilation process, the variable 'x' would be assigned a memory index in the stack, and all references to this 'x' would be resolved to that index.

Certainly this flat representation could be more optimal if we made use of an instruction that specifically incremented a particular variable, but the more general instruction type for addition still gets the job done.

Here are the implementations for some of these instructions:

// output
case op_output:
    cout << static_cast<int>(_stack.Top()) << endl;
    _stack.Pop();
    ++_instr;
    break;
// stack
case op_push_const:
    _stack.Push(_instr->Data()[0]);
    ++_instr;
    break;
case op_push_var:
    _stack.Push(_stack[_instr->Data()[0]]);
    ++_instr;
    break;
case op_assign:
    _stack[_instr->Data()[0]] = _stack.Top();
    _stack.Pop();
    ++_instr;
    break;
// arithmetic
case op_add:
{
    char top = _stack.Top();
    _stack.Pop();
    _stack.Top() += top;
}
    ++_instr;
    break;

The rest can be found in the downloadable source.


Program Flow

Up to this point scripts have only had a single path of execution. Each Instruction is only executed once in the order they are listed. What we will do now is incorporate instructions that actually move the instruction pointer to any position desired, rather than simply moving to the next one in the list. Such a change in position can either be absolute, or conditional. The concept is a simple yet powerful one, and will be the foundation for implementing the control structures of a higher-level language.

In the simplest case, an instruction to cause movement to a new position in the code would require a single parameter with a value of the destination index. This is an absolute jump:

case op_jump:
    _instr = _instrPtr + _instr->Data()[0];
    break;

When executed, this instruction will always lead the flow to the position indicated by its data. What we would like in addition to this is an instruction that will jump conditionally, determined by a Boolean value at the top of the stack. For this, we will have to adopt a Boolean convention for our data. To keep things consistent with what we're familiar with, false will refer to a value of zero, and true to any non-zero value.

case op_jump_if_true:
    if (_stack.Top() != 0)
        _instr = _instrPtr + _instr->Data()[0];
    else
        ++_instr;
    _stack.Pop();                
    break;

case op_jump_if_false:
    if (_stack.Top() == 0)
        _instr = _instrPtr + _instr->Data()[0];
    else
        ++_instr;
    _stack.Pop();
    break;

These two instructions will behave as stated, moving to a new position after examining the value at the top of the stack, and popping it off before they are done.


Higher-Level Constructs

An explanation of how such low-level jump instructions relate to higher-level control structures is due. I will now illustrate a few examples of C-style constructs and their equivalent jump instruction patterns in our bytecode. Note that although our parser doesn't support commenting, I will be using them in the example scripts shown.

The If-Else Clause:

C:

if (condition)
{
    // do something
}
else
{
    // do something else
}

Script:

// evaluate condition
jump_if_false A  // A corresponds to an appropriate value to reach the position marked A:
// do something
jump B
A:
// do something else
B:

The While Loop:

C:

while (condition)
{
    // do something
}

Script:

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

The Do-While Loop:

C:

do
{
    // do something
} while (condition);

Script:

A:
// do something
// evaluate condition
jump_if_true A

As you can imagine, dealing with the low-level jump instructions can be tedious, particularly when figuring out the appropriate index to jump to. A more robust development tool would certainly include a way to label positions in the code, and have jump instructions reference the labels, as I've shown in the examples above. But the idea here was to show that in the appropriate patterns our jump instructions could represent higher-level constructs.


Conditional Expressions

In order to drive our new conditional jumps, we need to have instructions that yield conditional results. Instructions performing value or logical comparison make the most sense in this case, and most will function much like the instructions implementing binary operations in the earlier section.

Unary:
op_not: performs a logical negation of the top of the stack

Binary:
Each of these compares the top two values on the stack, popping the top and returning an appropriate true/false to the new top.

op_and: performs logical conjunction
op_or: performs logical disjunction

op_equal
op_not_equal
op_greater
op_greater_equal
op_less
op_less_equal

This condition:

(x > 1) && (x <= 8)

Can be expressed as:

push_var x
push_const 1
greater
push_var x
push_const 8
less_equal
and

Where 'x' is again a placeholder for a variable index.

Here is code for two of these conditional evaluators:

case op_not:
    _stack.Top() = !_stack.Top();
    ++_instr;
    break;

case op_and:
{
    char top = _stack.Top();
    _stack.Pop();
    _stack.Top() = (_stack.Top() && top);
}
    ++_instr;
    break;

The rest of the instructions are similar to op_and, and can be found in the downloadable source.


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