Threaded-code and tail-call optimizations. Every good compiler can do it...

threaded.d

/**
 *  Simple threaded-code interpreter
 *  Practical on the follwoing compiler(s)/options 
 *  gdc -O2 and above (tested on venerable 4.6)
 *  ldc -O1 and above (tested with LLVM 3.3)
 *  Not usable on dmd - doesn't optimize tail-call to jump
*/
import std.typecons;

struct OpCode{
    bool function(State*) fn;
    uint data;
}
    
struct State{
    
    this(string s, OpCode[] codes...)
    {
        str = s;        
        opcodes = codes.dup;
    }
    uint pc, idx;
    string str;
    OpCode[] opcodes;
    Tuple!(uint, uint)[] stack; //pc-s stacked here
    
    bool exec()
    { 
        return opcodes[0].fn(&this); 
    }
    
    void push(uint pc)
    {
        stack ~= tuple(pc, idx);
    }
    
    bool pop()
    {
        if(stack.length == 0)
            return false;
        auto top = stack[$-1];
        stack = stack[0..$-1];
        pc = top[0];
        idx = top[1];
        return true;
    }
}
   
bool match(State* state)
{
    with(*state)
    {
        if(idx != str.length && str[idx] == opcodes[pc].data)
        {
            pc++;
            idx++;
        }
        else if(!pop())
            return false;
        //dispatch
        return opcodes[pc].fn(state);
    }
}

bool fork(State* state)
{
    with(*state)
    {
        push(opcodes[pc].data);
        pc++;
        //dispatch
        return opcodes[pc].fn(state);
    }
}

bool end(State* state)
{
    //full match semantics ;)
    with(*state)
        if(idx == str.length)
            return true;
        else if(pop())
            return opcodes[pc].fn(state);
        else
            return false;
}

void main()
{
    auto data = "ABABAB";
    auto machine = State(data, 
        OpCode(&match, 'A'), OpCode(&match, 'B'), OpCode(&fork, 0), 
        OpCode(&end, 0));
    //writefln("Matched: %s", machine.exec());
    assert(machine.exec());
}