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