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