code.kerkeslager.com Git - fur/blob - crossplatform_ir_generation.py

   1 import collections
   2
   3 import conversion
   4
   5 def flatten(xses):
   6     return tuple(x for xs in xses for x in xs)
   7
   8 CIRProgram = collections.namedtuple(
   9     'CIRProgram',
  10     (
  11         'entry_list',
  12     ),
  13 )
  14
  15 CIRLabel = collections.namedtuple(
  16     'CIRLabel',
  17     (
  18         'label',
  19     ),
  20 )
  21
  22 CIRInstruction = collections.namedtuple(
  23     'CIRInstruction',
  24     (
  25         'instruction',
  26         'argument',
  27     ),
  28 )
  29
  30 def generate_integer_literal(integer):
  31     return integer
  32
  33 def generate_string_literal(string):
  34     return '"{}"'.format(string)
  35
  36 def generate_symbol_literal(symbol):
  37     return 'sym({})'.format(symbol)
  38
  39 def generate_instruction_name_from_builtin(builtin):
  40     try:
  41         return {
  42             '__add__': 'add',
  43             '__integer_divide__': 'idiv',
  44             '__modular_divide__': 'mod',
  45             '__multiply__': 'mul',
  46             '__negate__': 'neg',
  47             '__subtract__': 'sub',
  48         }[builtin]
  49
  50     except KeyError:
  51         import ipdb; ipdb.set_trace()
  52
  53 def generate_function_call_expression(counters, expression):
  54     if isinstance(expression.function_expression, conversion.CPSBuiltinExpression):
  55         return (
  56             (),
  57             (
  58                 CIRInstruction(
  59                     instruction=generate_instruction_name_from_builtin(
  60                         expression.function_expression.symbol,
  61                     ),
  62                     argument=expression.argument_count,
  63                 ),
  64             )
  65         )
  66
  67     referenced_entry_list, instruction_list = generate_expression(
  68         counters,
  69         expression.function_expression,
  70     )
  71
  72     instruction_list += (
  73         CIRInstruction(
  74             instruction='call',
  75             argument=expression.argument_count,
  76         ),
  77     )
  78
  79     return referenced_entry_list, instruction_list
  80
  81 def generate_integer_literal_expression(counters, expression):
  82     referenced_entry_list = ()
  83     instruction_list = (CIRInstruction(
  84         instruction='push_integer',
  85         argument=generate_integer_literal(expression.integer),
  86     ),)
  87
  88     return referenced_entry_list, instruction_list
  89
  90 def escape_name(name):
  91     return name.replace('$','$$').replace('_','$')
  92
  93 def generate_lambda_expression(counters, expression):
  94     if expression.name is None:
  95         name = '__lambda__'
  96     else:
  97         name = escape_name(expression.name)
  98
  99     name_counter = counters.get(name, 0)
 100     counters[expression.name] = name_counter + 1
 101     label = '{}${}'.format(name, name_counter)
 102
 103     referenced_entry_list_list = []
 104     instruction_list_list = []
 105
 106     for statement in expression.statement_list:
 107         referenced_entry_list, instruction_list = generate_statement(counters, statement)
 108         referenced_entry_list_list.append(referenced_entry_list)
 109         instruction_list_list.append(instruction_list)
 110
 111     # Pop from the stack in reversed order, because arguments were pushed onto
 112     # the stack in order
 113     argument_bindings = tuple(
 114         CIRInstruction(instruction='pop', argument='sym({})'.format(arg))
 115         for arg in reversed(expression.argument_name_list)
 116     )
 117
 118     lambda_body = flatten(instruction_list_list)
 119     assert lambda_body[-1].instruction == 'drop'
 120     lambda_body = argument_bindings + lambda_body[:-1] + (CIRInstruction(instruction='return', argument=None),)
 121
 122     referenced_entry_list_list.append(
 123         (CIRLabel(label=label),) + lambda_body,
 124     )
 125
 126     instruction_list = (
 127         CIRInstruction(instruction='close', argument=label),
 128     )
 129
 130     return flatten(referenced_entry_list_list), instruction_list
 131
 132 def generate_list_construct_expression(counters, expression):
 133     referenced_entry_list = ()
 134     instruction_list = (CIRInstruction(
 135         instruction='list',
 136         argument=2,
 137     ),)
 138     return referenced_entry_list, instruction_list
 139
 140 def generate_string_literal_expression(counters, expression):
 141     referenced_entry_list = ()
 142     instruction_list = (CIRInstruction(
 143         instruction='push_string',
 144         argument=generate_string_literal(expression.string),
 145     ),)
 146
 147     return referenced_entry_list, instruction_list
 148
 149 def generate_structure_literal_expression(counters, expression):
 150     referenced_entry_list = ()
 151     instruction_list = (CIRInstruction(
 152         instruction='structure',
 153         argument=expression.field_count,
 154     ),)
 155
 156     return referenced_entry_list, instruction_list
 157
 158 def generate_symbol_expression(counters, expression):
 159     referenced_entry_list = ()
 160     instruction_list = (CIRInstruction(
 161         instruction='push',
 162         argument=generate_symbol_literal(expression.symbol),
 163     ),)
 164
 165     return referenced_entry_list, instruction_list
 166
 167 def generate_symbol_literal_expression(counters, expression):
 168     referenced_entry_list = ()
 169     instruction_list = (CIRInstruction(
 170         instruction='push_symbol',
 171         argument=generate_symbol_literal(expression.symbol),
 172     ),)
 173
 174     return referenced_entry_list, instruction_list
 175
 176 def generate_variable_expression(counters, expression):
 177     referenced_entry_list = ()
 178     instruction_list = (CIRInstruction(
 179         instruction='push',
 180         argument=generate_symbol_literal(expression.variable),
 181     ),)
 182
 183     return referenced_entry_list, instruction_list
 184
 185 def generate_expression(counters, expression):
 186     return {
 187         conversion.CPSFunctionCallExpression: generate_function_call_expression,
 188         conversion.CPSIfElseExpression: generate_if_else_expression,
 189         conversion.CPSIntegerLiteralExpression: generate_integer_literal_expression,
 190         conversion.CPSLambdaExpression: generate_lambda_expression,
 191         conversion.CPSListConstructExpression: generate_list_construct_expression,
 192         conversion.CPSStringLiteralExpression: generate_string_literal_expression,
 193         conversion.CPSStructureLiteralExpression: generate_structure_literal_expression,
 194         conversion.CPSSymbolExpression: generate_symbol_expression,
 195         conversion.CPSSymbolLiteralExpression: generate_symbol_literal_expression,
 196         conversion.CPSVariableExpression: generate_variable_expression,
 197     }[type(expression)](counters, expression)
 198
 199 def generate_expression_statement(counters, statement):
 200     referenced_entry_list, instruction_list = generate_expression(
 201         counters,
 202         statement.expression,
 203     )
 204
 205     instruction_list += (
 206         CIRInstruction(
 207             instruction='drop',
 208             argument=None,
 209         ),
 210     )
 211
 212     return referenced_entry_list, instruction_list
 213
 214 def generate_if_else_expression(counters, statement):
 215     if_counter = counters['if']
 216     counters['if'] += 1
 217
 218     referenced_entry_list_list = []
 219
 220     condition_referenced_entry_list, condition_instruction_list = generate_expression(
 221         counters,
 222         statement.condition_expression,
 223     )
 224
 225     if_instruction_list_list = []
 226     for if_statement in statement.if_statement_list:
 227         referenced_entry_list, instruction_list = generate_statement(counters, if_statement)
 228         referenced_entry_list_list.append(referenced_entry_list)
 229         if_instruction_list_list.append(instruction_list)
 230
 231     if_instruction_list = flatten(if_instruction_list_list)
 232     assert if_instruction_list[-1].instruction == 'drop'
 233     if_instruction_list = if_instruction_list[:-1]
 234
 235     else_instruction_list_list = []
 236
 237     for else_statement in statement.else_statement_list:
 238         referenced_entry_list, instruction_list = generate_statement(counters, else_statement)
 239         referenced_entry_list_list.append(referenced_entry_list)
 240         else_instruction_list_list.append(instruction_list)
 241
 242     else_instruction_list = flatten(else_instruction_list_list)
 243     assert else_instruction_list[-1].instruction == 'drop'
 244     else_instruction_list = else_instruction_list[:-1]
 245
 246     if_label = '__if${}__'.format(if_counter)
 247     else_label = '__else${}__'.format(if_counter)
 248     endif_label = '__endif${}__'.format(if_counter)
 249
 250     instruction_list = condition_instruction_list + (
 251         CIRInstruction(
 252             instruction='jump_if_false',
 253             argument=else_label,
 254         ),
 255         CIRInstruction(
 256             instruction='jump',
 257             argument=if_label,
 258         ),
 259         CIRLabel(label=if_label),
 260     ) + if_instruction_list + (
 261         CIRInstruction(
 262             instruction='jump',
 263             argument=endif_label,
 264         ),
 265         CIRLabel(label=else_label),
 266     ) + else_instruction_list + (
 267         CIRLabel(label=endif_label),
 268     )
 269
 270     return (
 271         condition_referenced_entry_list + flatten(referenced_entry_list_list),
 272         instruction_list,
 273     )
 274
 275 def generate_assignment_statement(counters, statement):
 276     referenced_entry_list, instruction_list = generate_expression(
 277         counters,
 278         statement.expression,
 279     )
 280
 281     instruction_list += (
 282         CIRInstruction(
 283             instruction='pop',
 284             argument=generate_symbol_literal(statement.target),
 285         ),
 286     )
 287
 288     return referenced_entry_list, instruction_list
 289
 290 def generate_push_statement(counters, statement):
 291     return generate_expression(counters, statement.expression)
 292
 293 def generate_variable_initialization_statement(counters, statement):
 294     referenced_entry_list, instruction_list = generate_expression(
 295         counters,
 296         statement.expression,
 297     )
 298
 299     instruction_list += (
 300         CIRInstruction(
 301             instruction='pop',
 302             argument=generate_symbol_literal(statement.variable),
 303         ),
 304     )
 305
 306     return referenced_entry_list, instruction_list
 307
 308 def generate_statement(counters, statement):
 309     return {
 310         conversion.CPSAssignmentStatement: generate_assignment_statement,
 311         conversion.CPSExpressionStatement: generate_expression_statement,
 312         conversion.CPSPushStatement: generate_push_statement,
 313         conversion.CPSVariableInitializationStatement: generate_variable_initialization_statement,
 314     }[type(statement)](counters, statement)
 315
 316 def generate(converted):
 317     referenced_entry_list_list = []
 318     instruction_list_list = []
 319     counters = {
 320         'if': 0,
 321     }
 322
 323     for statement in converted.statement_list:
 324         referenced_entry_list, instruction_list = generate_statement(counters, statement)
 325         referenced_entry_list_list.append(referenced_entry_list)
 326         instruction_list_list.append(instruction_list)
 327
 328     return CIRProgram(
 329         entry_list=flatten(referenced_entry_list_list) + (
 330             CIRLabel(label='__main__'),
 331         ) + flatten(instruction_list_list) + (
 332             CIRInstruction(instruction='end', argument=None),
 333         )
 334     )
 335
 336 NO_ARGUMENT_INSTRUCTIONS = set([
 337     'drop',
 338     'return',
 339 ])
 340
 341 def format_argument(arg):
 342     if arg is None:
 343         return 'nil'
 344     return arg
 345
 346 def output(program):
 347     lines = []
 348
 349     for entry in program.entry_list:
 350         if isinstance(entry, CIRInstruction):
 351             if entry.instruction in NO_ARGUMENT_INSTRUCTIONS and entry.argument is None:
 352                 lines.append('    {}'.format(entry.instruction))
 353             else:
 354                 lines.append('    {} {}'.format(entry.instruction, format_argument(entry.argument)))
 355
 356         if isinstance(entry, CIRLabel):
 357             lines.append('\n{}:'.format(entry.label))
 358
 359     return '\n'.join(lines).lstrip()