#!/usr/bin/env python

"""

A really simple virtual processor employing a simple set of instructions which

ignore low-level operations and merely concentrate on variable access, structure

access, structure allocation and function invocations.

Copyright (C) 2007, 2008 Paul Boddie <paul@boddie.org.uk>

This program is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free Software

Foundation; either version 3 of the License, or (at your option) any later

version.

This program is distributed in the hope that it will be useful, but WITHOUT

ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more

details.

You should have received a copy of the GNU General Public License along with

this program.  If not, see <http://www.gnu.org/licenses/>.

--------

The execution model of the virtual processor involves the following things:

  * Memory

  * PC (program counter) stack

  * Value stack

  * Frame stack (containing pointers to the value stack)

  * Current frame and arguments pointers

The memory contains constants, global variable references and program code.

The PC stack contains the return address associated with each function

invocation.

The value stack contains references to objects that are being manipulated, along

with pointers to previous stack frames.

The frame stack tracks the position of stack frames within the value stack.

"""

class IllegalInstruction(Exception):

    pass

class IllegalAddress(Exception):

    pass

class EmptyPCStack(Exception):

    pass

class EmptyMetadataStack(Exception):

    pass

class RSVPMachine:

    "A really simple virtual processor."

    def __init__(self, memory, pc=None, debug=0):

        """

        Initialise the processor with a 'memory' (a list of values containing

        instructions and data) and the optional program counter 'pc'.

        """

        self.memory = memory

        self.pc = pc or 0

        self.debug = debug

        self.pc_stack = []

        self.value_stack = []

        self.frame_stack = []

        self.frame_sp = 0

    def load(self, address):

        "Return the value at the given 'address'."

        try:

            return self.memory[address]

        except IndexError:

            raise IllegalAddress, address

    def save(self, address, value):

        "Save to the given 'address' the specified 'value'."

        try:

            self.memory[address] = value

        except IndexError:

            raise IllegalAddress, address

    def new(self, size):

        """

        Allocate space of the given 'size', returning the address of the space.

        """

        addr = len(self.memory)

        for i in range(0, size):

            self.memory.append(None)

        return addr

    def push(self, data):

        "Push 'data' onto the value stack."

        self.value_stack.append(data)

    def pull(self):

        "Pull a value from the value stack and return it."

        return self.value_stack.pop()

    def push_pc(self, data):

        "Push 'data' onto the PC stack."

        self.pc_stack.append(data)

    def pull_pc(self):

        "Pull a value from the PC stack and return it."

        try:

            return self.pc_stack.pop()

        except IndexError:

            raise EmptyPCStack

    def add_frame(self, data):

        "Add 'data' to the frame stack without updating the stack pointer."

        self.frame_stack.append(data)

    def push_frame(self, data):

        "Push 'data' onto the frame stack."

        self.frame_stack.append(data)

        self.frame_sp += 1

    def pull_frame(self):

        "Pull a value from the frame stack and return it."

        try:

            self.frame_sp -= 1

            return self.frame_stack.pop()

        except IndexError:

            raise EmptyMetadataStack

    def execute(self):

        "Execute code in the memory, starting from the current PC address."

        try:

            while 1:

                instruction = self.load(self.pc)

                if self.debug:

                    print "%8d %s" % (self.pc, instruction)

                method = getattr(self, instruction, None)

                if method is None:

                    raise IllegalInstruction, self.pc

                else:

                    method()

        except EmptyPCStack:

            pass

    def jump(self, addr, next):

        """

        Jump to the subroutine at (or identified by) 'addr'. If 'addr'

        identifies a library function then invoke the library function and set

        PC to 'next' afterwards; otherwise, set PC to 'addr'.

        """

        if isinstance(addr, str):

            getattr(self, addr)()

            self.pc = next

        else:

            self.push_pc(self.pc + 2)

            self.pc = addr

    # Instructions.

    def MakeFrame(self):

        top = len(self.value_stack)

        self.add_frame(top)

        self.pc += 1

    def DropFrame(self):

        result = self.pull()

        frame = self.pull_frame()

        self.value_stack = self.value_stack[:frame] # reset stack before call

        self.push(result)

        self.pc += 1

    def JumpWithFrame(self):

        addr = self.load(self.pc + 1)

        self.frame_sp += 1 # adopt the added frame

        self.jump(addr, self.pc + 2)

    def LoadName(self):

        """

        LoadName #n

        Load from position n in frame: get position n from the current stack

        frame, push the retrieved value onto the stack.

        """

        n = self.load(self.pc + 1)

        frame = self.frame_stack[self.frame_sp]

        self.push(self.value_stack[frame + n])

        self.pc += 2

    def StoreName(self):

        """

        StoreName #n

        Save to position n in frame: pull a value from the stack and set it as

        position n in the current stack frame.

        """

        n = self.load(self.pc + 1)

        frame = self.frame_stack[self.frame_sp]

        self.value_stack[frame + n] = self.pull()

        self.pc += 2

    LoadTemp = LoadName

    StoreTemp = StoreName

    def LoadConst(self):

        """

        LoadConst addr

        Load the reference to memory: get the address addr, push the value onto

        the stack.

        This is useful for loading constants.

        """

        addr = self.load(self.pc + 1)

        self.push(addr)

        self.pc += 2

    def LoadAttr(self):

        """

        LoadAttr #n

        Load from position n in reference: get the contents of position n in the

        memory referenced by the value on the top of the stack, replacing the

        value on the top of the stack with the retrieved value.

        """

        n = self.load(self.pc + 1)

        ref = self.pull()

        self.push(self.load(ref + n))

        self.pc += 2

    def StoreAttr(self):

        """

        StoreAttr #n

        Save to position n in reference: pull a value from the stack and save it

        to position n in the memory referenced by the next value on the stack,

        also removing the next value on the stack.

        """

        n = self.load(self.pc + 1)

        value = self.pull()

        self.save(self.pull() + n, value)

        self.pc += 2

    def LoadAddress(self):

        """

        LoadAddress addr, #n

        Load from position n in reference at addr: get the contents of position

        n in the memory referenced by addr, adding the retrieved value to the

        top of the stack.

        """

        red = self.load(self.pc + 1)

        n = self.load(self.pc + 2)

        self.push(self.load(ref + n))

        self.pc += 3

    def StoreAddress(self):

        """

        StoreAddress addr, #n

        Save to position n in reference at addr: pull a value from the stack and

        save it to position n in the memory referenced by addr, also removing

        the value on the top of the stack.

        """

        ref = self.load(self.pc + 1)

        n = self.load(self.pc + 2)

        value = self.pull()

        self.save(ref + n, value)

        self.pc += 3

    def Return(self):

        """

        Return

        Return to the address of the caller: pull a value from the PC stack and

        set it in the PC.

        """

        self.pc = self.pull_pc()

    def JumpIfTrue(self):

        """

        JumpIfTrue addr

        Jump to address addr if true: pull a value from the stack and if it

        represents a true value, jump to address addr.

        """

        addr = self.load(self.pc + 1)

        value = self.pull()

        if value:

            self.pc = addr

        else:

            self.pc += 2

    def JumpIfFalse(self):

        """

        JumpIfFalse addr

        Jump to address addr if false: pull a value from the stack and if it

        represents a false value, jump to address addr.

        """

        addr = self.load(self.pc + 1)

        value = self.pull()

        if not value:

            self.pc = addr

        else:

            self.pc += 2

    def StoreFrame(self):

        """

        StoreFrame #n

        Move the value from the top of the stack to the argument in position n:

        pull a value from the stack and store it in the argument frame at the

        given position.

        """

        pos = self.load(self.pc + 1)

        value = self.pull()

        frame = self.frame_stack[-1] # different from the current frame after MakeFrame

        self.value_stack[frame + pos] = value

        self.pc += 2

    # Library functions.

    def rsvp___printnl(self):

        print self.load(self.value_stack[-1])

    def rsvp___print(self):

        print self.load(self.value_stack[-1]),

    def int_____gt__(self):

        self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1]))

    def int_____sub__(self):

        result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1])

        addr = self.new(1)

        self.push(addr)

        self.save(addr, result)

    def int_____mul__(self):

        result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1])

        addr = self.new(1)

        self.push(addr)

        self.save(addr, result)

# vim: tabstop=4 expandtab shiftwidth=4