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