modelverse/kernel/modelverse_jit/tree_ir.py

# NOTE: NOP_LITERAL abuses a mechanic of the modelverse kernel. Specifically,
# whenever the `ModelverseKernel.execute_yields` method returns `None`, then
# the server built around it takes that as a hint that an instruction's phase
# has been completed. The server interrupts the kernel's thread of execution
# when it remarks that an instruction has completed a phase (i.e., when `None`
# is returned by `ModelverseKernel.execute_yields`) and proceeds to check for
# input and output.
#
# In assembly language, a nop is usually used as a point at which a thread of
# execution can be terminated. It follows from the paragraph above that what
# the interpreter does is more or less equivalent to placing nops after every
# instruction. It is worthwhile to remark that JIT-compiled code cannot rely
# on the kernel to interrupt the thread of execution automatically during a
# jitted function's execution -- jitted functions are considered equivalent
# to a single instruction as far as the kernel is concerned. A nop will be
# inserted _after_ the function call (if it is called from interpreted code)
# but that does not suffice for IO, which needs the input/output processing
# to be performed during function execution.
#
# For this reason, the JIT must strategically interrupt the execution of the
# functions it compiles. In other words, it must insert its own nops.
# Here comes the interesting part: a nop is equivalent to `yield None`,
# because that will persuade `ModelverseKernel.execute_yields` to relay the
# `None` marker value to the server, without terminating the current
# generator.

NOP_LITERAL = None
"""A literal that results in a nop during which execution may be interrupted
   when yielded."""

class Instruction(object):
    """A base class for instructions. An instruction is essentially a syntax
       node that must first be defined, and can only then be used."""

    def __init__(self):
        pass

    def has_result(self):
        """Tells if this instruction computes a result."""
        return True

    def has_definition(self):
        """Tells if this instruction requires a definition."""
        return True

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""

        if self.has_definition():
            raise NotImplementedError()
        else:
            code_generator.append_line('pass')

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""

        if self.has_result():
            return code_generator.get_result_name(self)
        else:
            return 'None'

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""

        return self

    def __str__(self):
        code_generator = PythonGenerator()
        self.generate_python_def(code_generator)
        return code_generator.code

class PythonGenerator(object):
    """Generates Python code from instructions."""

    def __init__(self):
        self.code = ''
        self.indentation_string = ' ' * 4
        self.indentation = 0
        self.result_value_dict = {}

    def append(self, text):
        """Appends the given string to this code generator."""

        self.code += text

    def append_indentation(self):
        """Appends indentation to the code generator."""

        self.append(self.indentation_string * self.indentation)

    def append_line(self, line=None):
        """Appends the indentation string followed by the given string (if any)
           and a newline to the code generator."""

        self.append_indentation()
        if line is not None:
            self.append(line)
        self.append('\n')

    def increase_indentation(self):
        """Increases the code generator's indentation by one indent."""

        self.indentation += 1

    def decrease_indentation(self):
        """Decreases the code generator's indentation by one indent."""

        self.indentation -= 1

    def get_result_name(self, instruction):
        """Gets the name of the given instruction's result variable."""

        if instruction not in self.result_value_dict:
            self.result_value_dict[instruction] = \
                'tmp' + str(len(self.result_value_dict))

        return self.result_value_dict[instruction]

    def append_definition(self, lhs, rhs):
        """Defines the first instruction's result variable as the second
           instruction's result."""

        self.append_line(
            self.get_result_name(lhs) + ' = ' + rhs.generate_python_use(self))

    def append_state_definition(self, lhs, opcode, args):
        """Appends a definition that queries the modelverse state."""

        self.append_line(
            "%s, = yield [('%s', [%s])]" % (
                self.get_result_name(lhs),
                opcode,
                ', '.join([arg_i.generate_python_use(self) for arg_i in args])))

class VoidInstruction(Instruction):
    """A base class for instructions that do not return a value."""

    def has_result(self):
        """Tells if this instruction computes a result."""
        return False

class EmptyInstruction(VoidInstruction):
    """Represents the empty instruction, which does nothing."""

    def has_definition(self):
        """Tells if this instruction requires a definition."""
        return False

class SelectInstruction(Instruction):
    """Represents a select-instruction: an instruction that defines one of two
       child instructions, and sets its result to the defined child's result."""

    def __init__(self, condition, if_clause, else_clause):
        Instruction.__init__(self)
        self.condition = condition
        self.if_clause = if_clause
        self.else_clause = else_clause

    def has_result(self):
        """Tells if this instruction computes a result."""
        return self.if_clause.has_result() or self.else_clause.has_result()

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        simple_cond = self.condition.simplify()
        simple_if = self.if_clause.simplify()
        simple_else = self.else_clause.simplify()
        if isinstance(simple_cond, LiteralInstruction):
            return simple_if if simple_cond.literal else simple_else
        else:
            return SelectInstruction(simple_cond, simple_if, simple_else)

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        if_has_result = self.has_result()
        if self.condition.has_definition():
            self.condition.generate_python_def(code_generator)

        code_generator.append_line(
            'if ' + self.condition.generate_python_use(code_generator) + ':')
        code_generator.increase_indentation()
        self.if_clause.generate_python_def(code_generator)
        if if_has_result:
            code_generator.append_definition(self, self.if_clause)
        code_generator.decrease_indentation()
        if self.else_clause.has_definition() or if_has_result:
            code_generator.append_line('else:')
            code_generator.increase_indentation()
            self.else_clause.generate_python_def(code_generator)
            if if_has_result:
                code_generator.append_definition(self, self.else_clause)
            code_generator.decrease_indentation()

class ReturnInstruction(VoidInstruction):
    """Represents a return-instruction."""

    def __init__(self, value):
        VoidInstruction.__init__(self)
        self.value = value

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""

        return LoopInstruction(self.value.simplify())

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""

        code_generator.append_line(
            'raise PrimitiveFinished(' +
            self.value.generate_python_use(code_generator) +
            ')')

class LoopInstruction(VoidInstruction):
    """Represents a loop-instruction, which loops until broken."""

    def __init__(self, body):
        VoidInstruction.__init__(self)
        self.body = body

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""

        return LoopInstruction(self.body.simplify())

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""

        code_generator.append_line('while True:')
        code_generator.increase_indentation()
        self.body.generate_python_def(code_generator)
        code_generator.decrease_indentation()

class BreakInstruction(VoidInstruction):
    """Represents a break-instruction."""

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""

        code_generator.append_line('break')

class ContinueInstruction(VoidInstruction):
    """Represents a continue-instruction."""

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""

        code_generator.append_line('continue')

class CompoundInstruction(Instruction):
    """Represents an instruction that evaluates two other instructions
       in order, and returns the second instruction's result."""

    def __init__(self, first, second):
        Instruction.__init__(self)
        self.first = first
        self.second = second

    def has_result(self):
        """Tells if this instruction has a result."""
        return self.second.has_result()

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""

        simple_fst, simple_snd = self.first.simplify(), self.second.simplify()
        if not simple_fst.has_definition():
            return simple_snd
        elif (not simple_snd.has_definition()) and (not simple_snd.has_result()):
            return simple_fst
        else:
            return CompoundInstruction(simple_fst, simple_snd)

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        self.first.generate_python_def(code_generator)
        self.second.generate_python_def(code_generator)
        if self.has_result():
            code_generator.append_definition(self, self.second)

class LiteralInstruction(Instruction):
    """Represents an integer, floating-point, string or Boolean literal."""
    def __init__(self, literal):
        Instruction.__init__(self)
        self.literal = literal

    def has_definition(self):
        """Tells if this instruction requires a definition."""
        return False

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        return repr(self.literal)

class StateInstruction(Instruction):
    """An instruction that accesses the modelverse state."""

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        raise NotImplementedError()

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        raise NotImplementedError()

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""

        args = self.get_arguments()
        for arg_i in args:
            if arg_i.has_definition():
                arg_i.generate_python_def(code_generator)

        code_generator.append_state_definition(self, self.get_opcode(), args)

class LocalInstruction(Instruction):
    """A base class for instructions that access local variables."""
    def __init__(self, name):
        Instruction.__init__(self)
        self.name = name

    def create_load(self):
        """Creates an instruction that loads the variable referenced by this instruction."""
        return LoadLocalInstruction(self.name)

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        return self.name

class StoreLocalInstruction(LocalInstruction):
    """An instruction that stores a value in a local variable."""
    def __init__(self, name, value):
        LocalInstruction.__init__(self, name)
        self.value = value

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return StoreLocalInstruction(self.name, self.value.simplify())

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""

        if self.value.has_definition():
            self.value.generate_python_def(code_generator)
        code_generator.append_line(
            '%s = %s' % (self.name, self.value.generate_python_use(code_generator)))

class LoadLocalInstruction(LocalInstruction):
    """An instruction that loads a value from a local variable."""
    def has_definition(self):
        """Tells if this instruction requires a definition."""
        return False

class DefineFunctionInstruction(LocalInstruction):
    """An instruction that defines a function."""
    def __init__(self, name, parameter_list, body):
        LocalInstruction.__init__(self, name)
        self.parameter_list = parameter_list
        self.body = body

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""

        code_generator.append_line('def %s(%s):' % (self.name, ', '.join(self.parameter_list)))
        code_generator.increase_indentation()
        self.body.generate_python_def(code_generator)
        code_generator.decrease_indentation()

class LoadIndexInstruction(Instruction):
    """An instruction that produces a value by indexing a specified expression with
       a given key."""
    def __init__(self, indexed, key):
        Instruction.__init__(self)
        self.indexed = indexed
        self.key = key

    def has_definition(self):
        """Tells if this instruction requires a definition."""
        return False

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        if self.indexed.has_definition():
            self.indexed.generate_python_def(code_generator)

        if self.key.has_definition():
            self.key.generate_python_def(code_generator)

        return "%s[%s]" % (
            self.indexed.generate_python_use(code_generator),
            self.key.generate_python_use(code_generator))

class NopInstruction(Instruction):
    """A nop instruction, which allows for the kernel's thread of execution to be interrupted."""

    def has_result(self):
        """Tells if this instruction computes a result."""
        return False

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""
        code_generator.append_line('yield %s' % repr(NOP_LITERAL))

class ReadValueInstruction(StateInstruction):
    """An instruction that reads a value from a node."""

    def __init__(self, node_id):
        StateInstruction.__init__(self)
        self.node_id = node_id

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return ReadValueInstruction(self.node_id.simplify())

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "RV"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id]

class ReadDictionaryValueInstruction(StateInstruction):
    """An instruction that reads a dictionary value."""

    def __init__(self, node_id, key):
        StateInstruction.__init__(self)
        self.node_id = node_id
        self.key = key

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return ReadDictionaryValueInstruction(
            self.node_id.simplify(),
            self.key.simplify())

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "RD"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id, self.key]

class ReadDictionaryEdgeInstruction(StateInstruction):
    """An instruction that reads a dictionary edge."""

    def __init__(self, node_id, key):
        StateInstruction.__init__(self)
        self.node_id = node_id
        self.key = key

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return ReadDictionaryEdgeInstruction(
            self.node_id.simplify(),
            self.key.simplify())

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "RDE"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id, self.key]

class CreateNodeInstruction(StateInstruction):
    """An instruction that creates an empty node."""

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "CN"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return []

class CreateDictionaryEdgeInstruction(StateInstruction):
    """An instruction that creates a dictionary edge."""

    def __init__(self, source_id, key, target_id):
        StateInstruction.__init__(self)
        self.source_id = source_id
        self.key = key
        self.target_id = target_id

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return CreateDictionaryEdgeInstruction(
            self.source_id.simplify(),
            self.key.simplify(),
            self.target_id.simplify())

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "CD"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.source_id, self.key, self.target_id]

class DeleteEdgeInstruction(StateInstruction):
    """An instruction that deletes an edge."""

    def __init__(self, edge_id):
        StateInstruction.__init__(self)
        self.edge_id = edge_id

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return DeleteEdgeInstruction(self.edge_id.simplify())

    def has_result(self):
        """Tells if this instruction computes a result."""
        return False

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "DE"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.edge_id]

def create_block(*statements):
    """Creates a block-statement from the given list of statements."""
    length = len(statements)
    if length == 0:
        return EmptyInstruction()
    elif length == 1:
        return statements[0]
    else:
        return CompoundInstruction(
            statements[0],
            create_block(*statements[1:]))

if __name__ == "__main__":
    example_tree = SelectInstruction(
        LiteralInstruction(True),
        LoopInstruction(
            CompoundInstruction(
                BreakInstruction(),
                CompoundInstruction(
                    EmptyInstruction(),
                    ContinueInstruction()
                )
            )
        ),
        ReturnInstruction(
            EmptyInstruction()))
    print(example_tree.simplify())