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

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.

Next : Program Flow