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

   1 import collections
   2
   3 import normalization
   4 import parsing # TODO Remove this import, as we should be normalizing everything before it gets here
   5
   6 CIntegerLiteral = collections.namedtuple(
   7     'CIntegerLiteral',
   8     [
   9         'value',
  10     ],
  11 )
  12
  13 CStringLiteral = collections.namedtuple(
  14     'CStringLiteral',
  15     [
  16         'index',
  17         'value',
  18     ],
  19 )
  20
  21 CVariableExpression = collections.namedtuple(
  22     'CVariableExpression',
  23     [
  24         'variable',
  25     ],
  26 )
  27
  28 CSymbolExpression = collections.namedtuple(
  29     'CSymbolExpression',
  30     [
  31         'symbol',
  32         'symbol_list_index',
  33     ],
  34 )
  35
  36 CStructureLiteralExpression = collections.namedtuple(
  37     'CStructureLiteralExpression',
  38     [
  39         'field_count',
  40         'symbol_list_variable',
  41         'value_list_variable',
  42     ],
  43 )
  44
  45 CDotExpression = collections.namedtuple(
  46     'CDotExpression',
  47     [
  48         'instance',
  49         'symbol',
  50         'symbol_list_index',
  51     ],
  52 )
  53
  54 CNegationExpression = collections.namedtuple(
  55     'CNegationExpression',
  56     [
  57         'value',
  58     ],
  59 )
  60
  61 CFunctionCallForFurInfixOperator = collections.namedtuple(
  62     'CFunctionCallForFurInfixOperator',
  63     [
  64         'metadata',
  65         'name',
  66     ],
  67 )
  68
  69 CPushStatement = collections.namedtuple(
  70     'CPushStatement',
  71     (
  72         'expression',
  73     ),
  74 )
  75
  76 CFunctionCallExpression = collections.namedtuple(
  77     'CFunctionCallExpression',
  78     [
  79         'function_expression',
  80         'argument_count',
  81     ],
  82 )
  83
  84 # TODO We are currently not changing variables, just preventing them from being accessed.
  85 CSymbolAssignmentStatement = collections.namedtuple(
  86     'CSymbolAssignmentStatement',
  87     [
  88         'target',
  89         'target_symbol_list_index',
  90         'expression',
  91     ],
  92 )
  93
  94 CArrayVariableInitializationStatement = collections.namedtuple(
  95     'CArrayVariableInitializationStatement',
  96     [
  97         'variable',
  98         'items',
  99     ],
 100 )
 101
 102 CSymbolArrayVariableInitializationStatement = collections.namedtuple(
 103     'CSymbolArrayVariableInitializationStatement',
 104     [
 105         'variable',
 106         'symbol_list',
 107         'symbol_list_indices',
 108     ],
 109 )
 110
 111 CVariableInitializationStatement = collections.namedtuple(
 112     'CVariableInitializationStatement',
 113     [
 114         'variable',
 115         'expression',
 116     ],
 117 )
 118
 119 CVariableReassignmentStatement = collections.namedtuple(
 120     'CVariableReassignmentStatement',
 121     [
 122         'variable',
 123         'expression',
 124     ],
 125 )
 126
 127 CExpressionStatement = collections.namedtuple(
 128     'CExpressionStatement',
 129     [
 130         'expression',
 131     ],
 132 )
 133
 134 CIfElseStatement = collections.namedtuple(
 135     'CIfElseStatement',
 136     [
 137         'condition_expression',
 138         'if_statement_list',
 139         'else_statement_list',
 140     ],
 141 )
 142
 143 CFunctionDeclaration = collections.namedtuple(
 144     'CFunctionDeclaration',
 145     [
 146         'name',
 147     ],
 148 )
 149
 150 # TODO If a function definition doesn't end with an expression, we have issues currently because we try to return statement.
 151 # TODO Closures currently wrap entire defining environment, even symbols that are not used, which makes garbage collection ineffective.
 152 CFunctionDefinition = collections.namedtuple(
 153     'CFunctionDefinition',
 154     [
 155         'name',
 156         'argument_name_list',
 157         'statement_list',
 158     ],
 159 )
 160
 161 CProgram = collections.namedtuple(
 162     'CProgram',
 163     [
 164         'builtin_set',
 165         'function_definition_list',
 166         'operator_declarations',
 167         'statements',
 168         'standard_libraries',
 169         'string_literal_list',
 170         'symbol_list',
 171     ],
 172 )
 173
 174 BUILTINS = {
 175     'concatenate':      [],
 176     'false':            [],
 177     'pow':              ['math.h'],
 178     'print':            ['stdio.h'],
 179     'true':             [],
 180 }
 181
 182 def transform_variable_expression(accumulators, expression):
 183     assert isinstance(expression, normalization.NormalVariableExpression)
 184     return CVariableExpression(variable=expression.variable)
 185
 186 def transform_string_literal_expression(accumulators, expression):
 187     value = expression.string
 188
 189     try:
 190         index = accumulators.string_literal_list.index(value)
 191     except ValueError:
 192         index = len(accumulators.string_literal_list)
 193         accumulators.string_literal_list.append(value)
 194
 195     return CStringLiteral(index=index, value=value)
 196
 197 def transform_symbol_expression(accumulators, expression):
 198     if expression.symbol in BUILTINS:
 199         accumulators.builtin_set.add(expression.symbol)
 200
 201     try:
 202         symbol_list_index = accumulators.symbol_list.index(expression.symbol)
 203     except ValueError:
 204         symbol_list_index = len(accumulators.symbol_list)
 205         accumulators.symbol_list.append(expression.symbol)
 206
 207     return CSymbolExpression(
 208         symbol=expression.symbol,
 209         symbol_list_index=symbol_list_index,
 210     )
 211
 212 CInfixDeclaration = collections.namedtuple(
 213     'CInfixDeclaration',
 214     [
 215         'name',
 216         'in_type',
 217         'out_type',
 218         'operator',
 219     ],
 220 )
 221
 222 FUR_INFIX_OPERATOR_TO_C_FUNCTION = {
 223     '++':   'concatenate',
 224 }
 225
 226 FUR_INFIX_OPERATOR_TO_C_INFIX_OPERATOR = {
 227     '+':    CInfixDeclaration(name='add', in_type='integer', out_type='integer', operator='+'),
 228     '-':    CInfixDeclaration(name='subtract', in_type='integer', out_type='integer', operator='-'),
 229     '*':    CInfixDeclaration(name='multiply', in_type='integer', out_type='integer', operator='*'),
 230     '//':   CInfixDeclaration(name='integerDivide', in_type='integer', out_type='integer', operator='/'),
 231     '%':    CInfixDeclaration(name='modularDivide', in_type='integer', out_type='integer', operator='%'),
 232     'and':  CInfixDeclaration(name='and', in_type='boolean', out_type='boolean', operator='&&'),
 233     'or':   CInfixDeclaration(name='or', in_type='boolean', out_type='boolean', operator='||'),
 234     '==':   CInfixDeclaration(name='equals', in_type='integer', out_type='boolean', operator='=='),
 235     '!=':   CInfixDeclaration(name='notEquals', in_type='integer', out_type='boolean', operator='!='),
 236     '<=':   CInfixDeclaration(name='lessThanOrEqual', in_type='integer', out_type='boolean', operator='<='),
 237     '>=':   CInfixDeclaration(name='greaterThanOrEqual', in_type='integer', out_type='boolean', operator='>='),
 238     '<':    CInfixDeclaration(name='lessThan', in_type='integer', out_type='boolean', operator='<'),
 239     '>':    CInfixDeclaration(name='greaterThan', in_type='integer', out_type='boolean', operator='>'),
 240 }
 241
 242 def transform_infix_operator_without_c_equivalent(accumulators, expression):
 243     return CFunctionCallForFurInfixOperator(
 244         metadata=expression.metadata,
 245         name='concatenate',
 246     )
 247
 248 def transform_infix_expression(accumulators, expression):
 249     if expression.operator in FUR_INFIX_OPERATOR_TO_C_FUNCTION:
 250         return transform_infix_operator_without_c_equivalent(accumulators, expression)
 251
 252     accumulators.operator_set.add(FUR_INFIX_OPERATOR_TO_C_INFIX_OPERATOR[expression.operator])
 253
 254     return CFunctionCallForFurInfixOperator(
 255         metadata=expression.metadata,
 256         name=FUR_INFIX_OPERATOR_TO_C_INFIX_OPERATOR[expression.operator].name,
 257     )
 258
 259 def transform_integer_literal_expression(accumulators, expression):
 260     return CIntegerLiteral(value=expression.integer)
 261
 262 def transform_negation_expression(accumulators, expression):
 263     return CNegationExpression(
 264         value=transform_expression(accumulators, expression.internal_expression),
 265     )
 266
 267 CListConstructExpression = collections.namedtuple(
 268     'CListConstructExpression',
 269     [
 270         'allocate',
 271     ],
 272 )
 273
 274 CListAppendStatement = collections.namedtuple(
 275     'CListAppendStatement',
 276     [
 277         'list_expression',
 278         'item_expression',
 279     ],
 280 )
 281
 282 CListGetExpression = collections.namedtuple(
 283     'CListGetExpression',
 284     [
 285         'list_expression',
 286         'index_expression',
 287     ],
 288 )
 289
 290 def transform_structure_literal_expression(accumulators, expression):
 291     return CStructureLiteralExpression(
 292         field_count=expression.field_count,
 293         symbol_list_variable=expression.symbol_list_variable,
 294         value_list_variable=expression.value_list_variable,
 295     )
 296
 297 def transform_dot_expression(accumulators, expression):
 298     try:
 299         symbol_list_index = accumulators.symbol_list.index(expression.field)
 300
 301     except ValueError:
 302         symbol_list_index = len(accumulators.symbol_list)
 303         accumulators.symbol_list.append(expression.field)
 304
 305     return CDotExpression(
 306         instance=transform_variable_expression(accumulators, expression.instance),
 307         symbol=expression.field,
 308         symbol_list_index=symbol_list_index,
 309     )
 310
 311 def transform_list_construct_expression(accumulators, expression):
 312     return CListConstructExpression(allocate=expression.allocate)
 313
 314 def transform_list_get_expression(accumulators, expression):
 315     return CListGetExpression(
 316         list_expression=transform_expression(accumulators, expression.list_expression),
 317         index_expression=transform_expression(accumulators, expression.index_expression),
 318     )
 319
 320 def transform_list_append_statement(accumulators, expression):
 321     return CListAppendStatement(
 322         list_expression=transform_expression(accumulators, expression.list_expression),
 323         item_expression=transform_expression(accumulators, expression.item_expression),
 324     )
 325
 326 def transform_expression(accumulators, expression):
 327     # TODO Clean up handlers for parsing expressions
 328     return {
 329         parsing.FurInfixExpression: transform_infix_expression,
 330         parsing.FurIntegerLiteralExpression: transform_integer_literal_expression,
 331         parsing.FurNegationExpression: transform_negation_expression,
 332         parsing.FurStringLiteralExpression: transform_string_literal_expression,
 333         normalization.NormalDotExpression: transform_dot_expression,
 334         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 335         normalization.NormalInfixExpression: transform_infix_expression,
 336         normalization.NormalIntegerLiteralExpression: transform_integer_literal_expression,
 337         normalization.NormalListConstructExpression: transform_list_construct_expression,
 338         normalization.NormalListGetExpression: transform_list_get_expression,
 339         normalization.NormalNegationExpression: transform_negation_expression,
 340         normalization.NormalStructureLiteralExpression: transform_structure_literal_expression,
 341         normalization.NormalStringLiteralExpression: transform_string_literal_expression,
 342         normalization.NormalSymbolExpression: transform_symbol_expression,
 343         normalization.NormalVariableExpression: transform_variable_expression,
 344     }[type(expression)](accumulators, expression)
 345
 346 def transform_symbol_assignment_statement(accumulators, assignment_statement):
 347     # TODO Check that target is not a builtin
 348     try:
 349         symbol_list_index = accumulators.symbol_list.index(assignment_statement.target)
 350     except ValueError:
 351         symbol_list_index = len(accumulators.symbol_list)
 352         accumulators.symbol_list.append(assignment_statement.target)
 353
 354     return CSymbolAssignmentStatement(
 355         target=assignment_statement.target,
 356         target_symbol_list_index=symbol_list_index,
 357         expression=transform_expression(
 358             accumulators,
 359             assignment_statement.expression,
 360         ),
 361     )
 362
 363 def transform_function_call_expression(accumulators, function_call):
 364     # TODO Use the symbol from SYMBOL LIST
 365     return CFunctionCallExpression(
 366         function_expression=transform_expression(accumulators, function_call.function_expression),
 367         argument_count=function_call.argument_count,
 368     )
 369
 370 def transform_expression_statement(accumulators, statement):
 371     return CExpressionStatement(
 372         expression=transform_expression(accumulators, statement.expression),
 373     )
 374
 375 def transform_if_else_statement(accumulators, statement):
 376     return CIfElseStatement(
 377         condition_expression=transform_expression(accumulators, statement.condition_expression),
 378         if_statement_list=tuple(transform_statement(accumulators, s) for s in statement.if_statement_list),
 379         else_statement_list=tuple(transform_statement(accumulators, s) for s in statement.else_statement_list),
 380     )
 381
 382 def transform_array_variable_initialization_statement(accumulators, statement):
 383     return CArrayVariableInitializationStatement(
 384         variable=statement.variable,
 385         items=tuple(transform_expression(accumulators, i) for i in statement.items),
 386     )
 387
 388 def transform_symbol_array_variable_initialization_statement(accumulators, statement):
 389     symbol_list_indices = []
 390
 391     for symbol in statement.symbol_list:
 392         try:
 393             symbol_list_index = accumulators.symbol_list.index(symbol)
 394         except ValueError:
 395             symbol_list_index = len(accumulators.symbol_list)
 396             accumulators.symbol_list.append(symbol)
 397
 398         symbol_list_indices.append(symbol_list_index)
 399
 400     return CSymbolArrayVariableInitializationStatement(
 401         variable=statement.variable,
 402         symbol_list=statement.symbol_list,
 403         symbol_list_indices=tuple(symbol_list_indices),
 404     )
 405
 406 def transform_variable_initialization_statement(accumulators, statement):
 407     return CVariableInitializationStatement(
 408         variable=statement.variable,
 409         expression=transform_expression(accumulators, statement.expression),
 410     )
 411
 412 def transform_variable_reassignment_statement(accumulators, statement):
 413     return CVariableReassignmentStatement(
 414         variable=statement.variable,
 415         expression=transform_expression(accumulators, statement.expression),
 416     )
 417
 418 def transform_function_definition_statement(accumulators, statement):
 419     # TODO Allow defining the same function in different contexts
 420     if any(fd.name == statement.name for fd in accumulators.function_definition_list):
 421         raise Exception('A function with name "{}" already exists'.format(statement.name))
 422
 423     # TODO Add argument names to the symbol table
 424     accumulators.function_definition_list.append(CFunctionDefinition(
 425         name=statement.name,
 426         argument_name_list=statement.argument_name_list,
 427         statement_list=tuple(transform_statement(accumulators, s) for s in statement.statement_list)
 428     ))
 429
 430     return CFunctionDeclaration(name=statement.name)
 431
 432 def transform_push_statement(accumulators, statement):
 433     return CPushStatement(expression=transform_expression(accumulators, statement.expression))
 434
 435 def transform_statement(accumulators, statement):
 436     return {
 437         parsing.FurExpressionStatement: transform_expression_statement,
 438         normalization.NormalArrayVariableInitializationStatement: transform_array_variable_initialization_statement,
 439         normalization.NormalAssignmentStatement: transform_symbol_assignment_statement,
 440         normalization.NormalExpressionStatement: transform_expression_statement,
 441         normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement,
 442         normalization.NormalIfElseStatement: transform_if_else_statement,
 443         normalization.NormalListAppendStatement: transform_list_append_statement,
 444         normalization.NormalPushStatement: transform_push_statement,
 445         normalization.NormalSymbolArrayVariableInitializationStatement: transform_symbol_array_variable_initialization_statement,
 446         normalization.NormalVariableInitializationStatement: transform_variable_initialization_statement,
 447         normalization.NormalVariableReassignmentStatement: transform_variable_reassignment_statement,
 448     }[type(statement)](accumulators, statement)
 449
 450
 451 Accumulators = collections.namedtuple(
 452     'Accumulators',
 453     [
 454         'builtin_set',
 455         'function_definition_list',
 456         'operator_set',
 457         'symbol_list',
 458         'string_literal_list',
 459     ],
 460 )
 461
 462 def transform(program):
 463     accumulators = Accumulators(
 464         builtin_set=set(),
 465         function_definition_list=[],
 466         operator_set=set(),
 467         symbol_list=[],
 468         string_literal_list=[],
 469     )
 470
 471     statement_list = [
 472         transform_statement(accumulators, statement) for statement in program.statement_list
 473     ]
 474
 475     standard_library_set = set()
 476     for builtin in accumulators.builtin_set:
 477         for standard_library in BUILTINS[builtin]:
 478             standard_library_set.add(standard_library)
 479
 480     return CProgram(
 481         builtin_set=accumulators.builtin_set,
 482         function_definition_list=accumulators.function_definition_list,
 483         operator_declarations=tuple(sorted(accumulators.operator_set)),
 484         statements=statement_list,
 485         standard_libraries=standard_library_set,
 486         string_literal_list=accumulators.string_literal_list,
 487         symbol_list=accumulators.symbol_list,
 488     )
 489
 490
 491 if __name__ == '__main__':
 492     import unittest
 493
 494     unittest.main()