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     return CFunctionCallForFurInfixOperator(
 247         name=FUR_INFIX_OPERATOR_TO_C_INFIX_OPERATOR[expression.operator].name,
 248         left=transform_expression(accumulators, expression.left),
 249         right=transform_expression(accumulators, expression.right),
 250     )
 251
 252 def transform_infix_operator_without_c_equivalent(accumulators, expression):
 253     return CFunctionCallForFurInfixOperator(
 254         name='concatenate',
 255         left=transform_expression(accumulators, expression.left),
 256         right=transform_expression(accumulators, expression.right),
 257     )
 258 def transform_infix_expression(accumulators, expression):
 259     if expression.operator in FUR_INFIX_OPERATOR_TO_C_FUNCTION:
 260         return transform_infix_operator_without_c_equivalent(accumulators, expression)
 261
 262     if expression.order == 'comparison_level':
 263         return transform_comparison_level_expression(accumulators, expression)
 264
 265     accumulators.operator_set.add(FUR_INFIX_OPERATOR_TO_C_INFIX_OPERATOR[expression.operator])
 266
 267     return CFunctionCallForFurInfixOperator(
 268         name=FUR_INFIX_OPERATOR_TO_C_INFIX_OPERATOR[expression.operator].name,
 269         left=transform_expression(accumulators, expression.left),
 270         right=transform_expression(accumulators, expression.right),
 271     )
 272
 273 def transform_integer_literal_expression(accumulators, expression):
 274     return CIntegerLiteral(value=expression.integer)
 275
 276 def transform_negation_expression(accumulators, expression):
 277     return CNegationExpression(
 278         value=transform_expression(accumulators, expression.internal_expression),
 279     )
 280
 281 CListConstructExpression = collections.namedtuple(
 282     'CListConstructExpression',
 283     [
 284         'allocate',
 285     ],
 286 )
 287
 288 CListAppendStatement = collections.namedtuple(
 289     'CListAppendStatement',
 290     [
 291         'list_expression',
 292         'item_expression',
 293     ],
 294 )
 295
 296 CListGetExpression = collections.namedtuple(
 297     'CListGetExpression',
 298     [
 299         'list_expression',
 300         'index_expression',
 301     ],
 302 )
 303
 304 def transform_structure_literal_expression(accumulators, expression):
 305     return CStructureLiteralExpression(
 306         field_count=expression.field_count,
 307         symbol_list_variable=expression.symbol_list_variable,
 308         value_list_variable=expression.value_list_variable,
 309     )
 310
 311 def transform_dot_expression(accumulators, expression):
 312     try:
 313         symbol_list_index = accumulators.symbol_list.index(expression.field)
 314
 315     except ValueError:
 316         symbol_list_index = len(accumulators.symbol_list)
 317         accumulators.symbol_list.append(expression.field)
 318
 319     return CDotExpression(
 320         instance=transform_variable_expression(accumulators, expression.instance),
 321         symbol=expression.field,
 322         symbol_list_index=symbol_list_index,
 323     )
 324
 325 def transform_list_construct_expression(accumulators, expression):
 326     return CListConstructExpression(allocate=expression.allocate)
 327
 328 def transform_list_get_expression(accumulators, expression):
 329     return CListGetExpression(
 330         list_expression=transform_expression(accumulators, expression.list_expression),
 331         index_expression=transform_expression(accumulators, expression.index_expression),
 332     )
 333
 334 def transform_list_append_statement(accumulators, expression):
 335     return CListAppendStatement(
 336         list_expression=transform_expression(accumulators, expression.list_expression),
 337         item_expression=transform_expression(accumulators, expression.item_expression),
 338     )
 339
 340 def transform_expression(accumulators, expression):
 341     # TODO Clean up handlers for parsing expressions
 342     return {
 343         parsing.FurInfixExpression: transform_infix_expression,
 344         parsing.FurIntegerLiteralExpression: transform_integer_literal_expression,
 345         parsing.FurNegationExpression: transform_negation_expression,
 346         parsing.FurStringLiteralExpression: transform_string_literal_expression,
 347         normalization.NormalDotExpression: transform_dot_expression,
 348         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 349         normalization.NormalInfixExpression: transform_infix_expression,
 350         normalization.NormalIntegerLiteralExpression: transform_integer_literal_expression,
 351         normalization.NormalListConstructExpression: transform_list_construct_expression,
 352         normalization.NormalListGetExpression: transform_list_get_expression,
 353         normalization.NormalNegationExpression: transform_negation_expression,
 354         normalization.NormalStructureLiteralExpression: transform_structure_literal_expression,
 355         normalization.NormalStringLiteralExpression: transform_string_literal_expression,
 356         normalization.NormalSymbolExpression: transform_symbol_expression,
 357         normalization.NormalVariableExpression: transform_variable_expression,
 358     }[type(expression)](accumulators, expression)
 359
 360 def transform_symbol_assignment_statement(accumulators, assignment_statement):
 361     # TODO Check that target is not a builtin
 362     try:
 363         symbol_list_index = accumulators.symbol_list.index(assignment_statement.target)
 364     except ValueError:
 365         symbol_list_index = len(accumulators.symbol_list)
 366         accumulators.symbol_list.append(assignment_statement.target)
 367
 368     return CSymbolAssignmentStatement(
 369         target=assignment_statement.target,
 370         target_symbol_list_index=symbol_list_index,
 371         expression=transform_expression(
 372             accumulators,
 373             assignment_statement.expression,
 374         ),
 375     )
 376
 377 def transform_function_call_expression(accumulators, function_call):
 378     # TODO Use the symbol from SYMBOL LIST
 379     return CFunctionCallExpression(
 380         function_expression=transform_expression(accumulators, function_call.function_expression),
 381         argument_count=function_call.argument_count,
 382     )
 383
 384 def transform_expression_statement(accumulators, statement):
 385     return CExpressionStatement(
 386         expression=transform_expression(accumulators, statement.expression),
 387     )
 388
 389 def transform_if_else_statement(accumulators, statement):
 390     return CIfElseStatement(
 391         condition_expression=transform_expression(accumulators, statement.condition_expression),
 392         if_statement_list=tuple(transform_statement(accumulators, s) for s in statement.if_statement_list),
 393         else_statement_list=tuple(transform_statement(accumulators, s) for s in statement.else_statement_list),
 394     )
 395
 396 def transform_array_variable_initialization_statement(accumulators, statement):
 397     return CArrayVariableInitializationStatement(
 398         variable=statement.variable,
 399         items=tuple(transform_expression(accumulators, i) for i in statement.items),
 400     )
 401
 402 def transform_symbol_array_variable_initialization_statement(accumulators, statement):
 403     symbol_list_indices = []
 404
 405     for symbol in statement.symbol_list:
 406         try:
 407             symbol_list_index = accumulators.symbol_list.index(symbol)
 408         except ValueError:
 409             symbol_list_index = len(accumulators.symbol_list)
 410             accumulators.symbol_list.append(symbol)
 411
 412         symbol_list_indices.append(symbol_list_index)
 413
 414     return CSymbolArrayVariableInitializationStatement(
 415         variable=statement.variable,
 416         symbol_list=statement.symbol_list,
 417         symbol_list_indices=tuple(symbol_list_indices),
 418     )
 419
 420 def transform_variable_initialization_statement(accumulators, statement):
 421     return CVariableInitializationStatement(
 422         variable=statement.variable,
 423         expression=transform_expression(accumulators, statement.expression),
 424     )
 425
 426 def transform_variable_reassignment_statement(accumulators, statement):
 427     return CVariableReassignmentStatement(
 428         variable=statement.variable,
 429         expression=transform_expression(accumulators, statement.expression),
 430     )
 431
 432 def transform_function_definition_statement(accumulators, statement):
 433     # TODO Allow defining the same function in different contexts
 434     if any(fd.name == statement.name for fd in accumulators.function_definition_list):
 435         raise Exception('A function with name "{}" already exists'.format(statement.name))
 436
 437     # TODO Add argument names to the symbol table
 438     accumulators.function_definition_list.append(CFunctionDefinition(
 439         name=statement.name,
 440         argument_name_list=statement.argument_name_list,
 441         statement_list=tuple(transform_statement(accumulators, s) for s in statement.statement_list)
 442     ))
 443
 444     return CFunctionDeclaration(name=statement.name)
 445
 446 def transform_push_statement(accumulators, statement):
 447     return CPushStatement(expression=transform_expression(accumulators, statement.expression))
 448
 449 def transform_statement(accumulators, statement):
 450     return {
 451         parsing.FurExpressionStatement: transform_expression_statement,
 452         normalization.NormalArrayVariableInitializationStatement: transform_array_variable_initialization_statement,
 453         normalization.NormalAssignmentStatement: transform_symbol_assignment_statement,
 454         normalization.NormalExpressionStatement: transform_expression_statement,
 455         normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement,
 456         normalization.NormalIfElseStatement: transform_if_else_statement,
 457         normalization.NormalListAppendStatement: transform_list_append_statement,
 458         normalization.NormalPushStatement: transform_push_statement,
 459         normalization.NormalSymbolArrayVariableInitializationStatement: transform_symbol_array_variable_initialization_statement,
 460         normalization.NormalVariableInitializationStatement: transform_variable_initialization_statement,
 461         normalization.NormalVariableReassignmentStatement: transform_variable_reassignment_statement,
 462     }[type(statement)](accumulators, statement)
 463
 464
 465 Accumulators = collections.namedtuple(
 466     'Accumulators',
 467     [
 468         'builtin_set',
 469         'function_definition_list',
 470         'operator_set',
 471         'symbol_list',
 472         'string_literal_list',
 473     ],
 474 )
 475
 476 def transform(program):
 477     accumulators = Accumulators(
 478         builtin_set=set(),
 479         function_definition_list=[],
 480         operator_set=set(),
 481         symbol_list=[],
 482         string_literal_list=[],
 483     )
 484
 485     statement_list = [
 486         transform_statement(accumulators, statement) for statement in program.statement_list
 487     ]
 488
 489     standard_library_set = set()
 490     for builtin in accumulators.builtin_set:
 491         for standard_library in BUILTINS[builtin]:
 492             standard_library_set.add(standard_library)
 493
 494     return CProgram(
 495         builtin_set=accumulators.builtin_set,
 496         function_definition_list=accumulators.function_definition_list,
 497         operator_declarations=tuple(sorted(accumulators.operator_set)),
 498         statements=statement_list,
 499         standard_libraries=standard_library_set,
 500         string_literal_list=accumulators.string_literal_list,
 501         symbol_list=accumulators.symbol_list,
 502     )
 503
 504
 505 if __name__ == '__main__':
 506     import unittest
 507
 508     unittest.main()