# 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 get_result_name_override(self): """Gets a value that overrides the code generator's result name for this instruction if it is not None.""" return None 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 str(code_generator) 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.append(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, advised_name=None): """Gets the name of the given instruction's result variable.""" if instruction not in self.result_value_dict: override_name = instruction.get_result_name_override() if override_name is not None: self.result_value_dict[instruction] = override_name elif advised_name is not None: self.result_value_dict[instruction] = advised_name else: 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_move_definition(self, lhs, rhs): """First defines the second instruction, then defines the first instruction as the result of the second.""" if rhs.has_definition(): # Retrieve the result name for the lhs. lhs_result_name = self.get_result_name(lhs) # Encourage the rhs to take on the same result name as the lhs. rhs_result_name = self.get_result_name(rhs, lhs_result_name) # Generate the rhs' definition. rhs.generate_python_def(self) # Only perform an assignment if it's truly necessary. if lhs_result_name != rhs_result_name: self.append_definition(lhs, rhs) else: self.append_definition(lhs, rhs) 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]))) def __str__(self): return ''.join(self.code) 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() if if_has_result: code_generator.append_move_definition(self, self.if_clause) else: self.if_clause.generate_python_def(code_generator) code_generator.decrease_indentation() else_has_def = self.else_clause.has_definition() if else_has_def or if_has_result: code_generator.append_line('else:') code_generator.increase_indentation() if if_has_result: code_generator.append_move_definition(self, self.else_clause) else: self.else_clause.generate_python_def(code_generator) 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 ReturnInstruction(self.value.simplify()) def generate_python_def(self, code_generator): """Generates Python code for this instruction.""" if self.value.has_definition(): self.value.generate_python_def(code_generator) code_generator.append_line( 'raise PrimitiveFinished(' + self.value.generate_python_use(code_generator) + ')') class RaiseInstruction(VoidInstruction): """An instruction that raises an error.""" def __init__(self, value): VoidInstruction.__init__(self) self.value = value def simplify(self): """Applies basic simplification to this instruction and its children.""" return RaiseInstruction(self.value.simplify()) def generate_python_def(self, code_generator): """Generates Python code for this instruction.""" self.value.generate_python_def(code_generator) code_generator.append_line( 'raise ' + self.value.generate_python_use(code_generator)) class CallInstruction(Instruction): """An instruction that performs a simple call.""" def __init__(self, target, argument_list): Instruction.__init__(self) self.target = target self.argument_list = argument_list def simplify(self): """Applies basic simplification to this instruction and its children.""" return CallInstruction( self.target.simplify(), [arg.simplify() for arg in self.argument_list]) def generate_python_def(self, code_generator): """Generates Python code for this instruction.""" if self.target.has_definition(): self.target.generate_python_def(code_generator) for arg in self.argument_list: if arg.has_definition(): arg.generate_python_def(code_generator) code_generator.append_line( '%s = %s(%s) ' % ( code_generator.get_result_name(self), self.target.generate_python_use(code_generator), ', '.join([arg.generate_python_use(code_generator) for arg in self.argument_list]))) class BinaryInstruction(Instruction): """An instruction that performs a binary operation.""" def __init__(self, lhs, operator, rhs): Instruction.__init__(self) self.lhs = lhs self.operator = operator self.rhs = rhs def has_definition(self): """Tells if this instruction requires a definition.""" return self.lhs.has_definition() or self.rhs.has_definition() def simplify(self): """Applies basic simplification to this instruction and its children.""" simple_lhs, simple_rhs = self.lhs.simplify(), self.rhs.simplify() return BinaryInstruction(simple_lhs, self.operator, simple_rhs) 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 '%s %s %s' % ( self.lhs.generate_python_use(code_generator), self.operator, self.rhs.generate_python_use(code_generator)) 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.lhs.has_definition(): self.lhs.generate_python_def(code_generator) if self.rhs.has_definition(): self.rhs.generate_python_def(code_generator) elif self.rhs.has_definition(): self.rhs.generate_python_def(code_generator) else: code_generator.append_line('pass') 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 1:') 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) code_generator.append_move_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 get_result_name_override(self): """Gets a value that overrides the code generator's result name for this instruction if it is not None.""" return self.name def create_load(self): """Creates an instruction that loads the variable referenced by this instruction.""" return LoadLocalInstruction(self.name) def create_store(self, value): """Creates an instruction that stores the given value in the variable referenced by this instruction.""" return StoreLocalInstruction(self.name, value) 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.""" code_generator.append_move_definition(self, self.value) 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 LocalExistsInstruction(LocalInstruction): """An instruction that checks if a local variable exists.""" 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 "'%s' in locals()" % self.name 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 DeleteNodeInstruction(StateInstruction): """An instruction that deletes 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 DeleteNodeInstruction(self.node_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 "DN" def get_arguments(self): """Gets this state instruction's argument list.""" return [self.node_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())