Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
84 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

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


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.



Next : Demonstration