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

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.

Next : Relocation of Execution