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