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     'false':            [],
 144     'pow':              ['math.h'],
 145     'print':            ['stdio.h'],
 146     'true':             [],
 147 }
 148
 149 def transform_variable_expression(accumulators, expression):
 150     return CVariableExpression(variable=expression.variable)
 151
 152 def transform_string_literal_expression(accumulators, expression):
 153     value = expression.string
 154
 155     try:
 156         index = accumulators.string_literal_list.index(value)
 157     except ValueError:
 158         index = len(accumulators.string_literal_list)
 159         accumulators.string_literal_list.append(value)
 160
 161     return CStringLiteral(index=index, value=value)
 162
 163 def transform_symbol_expression(accumulators, expression):
 164     if expression.symbol in BUILTINS:
 165         accumulators.builtin_set.add(expression.symbol)
 166
 167     try:
 168         symbol_list_index = accumulators.symbol_list.index(expression.symbol)
 169     except ValueError:
 170         symbol_list_index = len(accumulators.symbol_list)
 171         accumulators.symbol_list.append(expression.symbol)
 172
 173     return CSymbolExpression(
 174         symbol=expression.symbol,
 175         symbol_list_index=symbol_list_index,
 176     )
 177
 178 CInfixDeclaration = collections.namedtuple(
 179     'CInfixDeclaration',
 180     [
 181         'name',
 182         'in_type',
 183         'out_type',
 184         'operator',
 185     ],
 186 )
 187
 188 INFIX_OPERATOR_TO_DECLARATION = {
 189     '+':    CInfixDeclaration(name='add', in_type='integer', out_type='integer', operator='+'),
 190     '-':    CInfixDeclaration(name='subtract', in_type='integer', out_type='integer', operator='-'),
 191     '*':    CInfixDeclaration(name='multiply', in_type='integer', out_type='integer', operator='*'),
 192     '//':   CInfixDeclaration(name='integerDivide', in_type='integer', out_type='integer', operator='/'),
 193     '%':    CInfixDeclaration(name='modularDivide', in_type='integer', out_type='integer', operator='%'),
 194     'and':  CInfixDeclaration(name='and', in_type='boolean', out_type='boolean', operator='&&'),
 195     'or':   CInfixDeclaration(name='or', in_type='boolean', out_type='boolean', operator='||'),
 196     '==':   CInfixDeclaration(name='equals', in_type='integer', out_type='boolean', operator='=='),
 197     '!=':   CInfixDeclaration(name='notEquals', in_type='integer', out_type='boolean', operator='!='),
 198     '<=':   CInfixDeclaration(name='lessThanOrEqual', in_type='integer', out_type='boolean', operator='<='),
 199     '>=':   CInfixDeclaration(name='greaterThanOrEqual', in_type='integer', out_type='boolean', operator='>='),
 200     '<':    CInfixDeclaration(name='lessThan', in_type='integer', out_type='boolean', operator='<'),
 201     '>':    CInfixDeclaration(name='greaterThan', in_type='integer', out_type='boolean', operator='>'),
 202 }
 203
 204 def transform_comparison_level_expression(accumulators, expression):
 205     accumulators.operator_set.add(INFIX_OPERATOR_TO_DECLARATION[expression.operator])
 206
 207     # Transform expressions like 1 < 2 < 3 into expressions like 1 < 2 && 2 < 3
 208     if isinstance(expression.left, parsing.FurInfixExpression) and expression.left.order == 'comparison_level':
 209         left = transform_comparison_level_expression(
 210             accumulators,
 211             expression.left
 212         )
 213
 214         middle = left.right
 215
 216         right = transform_expression(
 217             accumulators,
 218             expression.right,
 219         )
 220
 221         # TODO Don't evaluate the middle expression twice
 222         return CFunctionCallForFurInfixOperator(
 223             name='and',
 224             left=left,
 225             right=CFunctionCallForFurInfixOperator(
 226                 name=INFIX_OPERATOR_TO_DECLARATION[expression.operator].name,
 227                 left=middle,
 228                 right=right,
 229             ),
 230         )
 231
 232     return CFunctionCallForFurInfixOperator(
 233         name=INFIX_OPERATOR_TO_DECLARATION[expression.operator].name,
 234         left=transform_expression(accumulators, expression.left),
 235         right=transform_expression(accumulators, expression.right),
 236     )
 237
 238 def transform_infix_expression(accumulators, expression):
 239     if expression.order == 'comparison_level':
 240         return transform_comparison_level_expression(accumulators, expression)
 241
 242     accumulators.operator_set.add(INFIX_OPERATOR_TO_DECLARATION[expression.operator])
 243
 244     return CFunctionCallForFurInfixOperator(
 245         name=INFIX_OPERATOR_TO_DECLARATION[expression.operator].name,
 246         left=transform_expression(accumulators, expression.left),
 247         right=transform_expression(accumulators, expression.right),
 248     )
 249
 250 def transform_integer_literal_expression(accumulators, expression):
 251     return CIntegerLiteral(value=expression.integer)
 252
 253 def transform_negation_expression(accumulators, expression):
 254     return CNegationExpression(
 255         value=transform_expression(accumulators, expression.internal_expression),
 256     )
 257
 258 CListConstructExpression = collections.namedtuple(
 259     'CListConstructExpression',
 260     [
 261         'allocate',
 262     ],
 263 )
 264
 265 CListAppendStatement = collections.namedtuple(
 266     'CListAppendStatement',
 267     [
 268         'list_expression',
 269         'item_expression',
 270     ],
 271 )
 272
 273 CListGetExpression = collections.namedtuple(
 274     'CListGetExpression',
 275     [
 276         'list_expression',
 277         'index_expression',
 278     ],
 279 )
 280
 281 def transform_list_construct_expression(accumulators, expression):
 282     return CListConstructExpression(allocate=expression.allocate)
 283
 284 def transform_list_get_expression(accumulators, expression):
 285     return CListGetExpression(
 286         list_expression=transform_expression(accumulators, expression.list_expression),
 287         index_expression=transform_expression(accumulators, expression.index_expression),
 288     )
 289
 290 def transform_list_append_statement(accumulators, expression):
 291     return CListAppendStatement(
 292         list_expression=transform_expression(accumulators, expression.list_expression),
 293         item_expression=transform_expression(accumulators, expression.item_expression),
 294     )
 295
 296 def transform_expression(accumulators, expression):
 297     # TODO Clean up handlers for parsing expressions
 298     return {
 299         parsing.FurInfixExpression: transform_infix_expression,
 300         parsing.FurIntegerLiteralExpression: transform_integer_literal_expression,
 301         parsing.FurNegationExpression: transform_negation_expression,
 302         parsing.FurStringLiteralExpression: transform_string_literal_expression,
 303         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 304         normalization.NormalInfixExpression: transform_infix_expression,
 305         normalization.NormalIntegerLiteralExpression: transform_integer_literal_expression,
 306         normalization.NormalListConstructExpression: transform_list_construct_expression,
 307         normalization.NormalListGetExpression: transform_list_get_expression,
 308         normalization.NormalNegationExpression: transform_negation_expression,
 309         normalization.NormalStringLiteralExpression: transform_string_literal_expression,
 310         normalization.NormalSymbolExpression: transform_symbol_expression,
 311         normalization.NormalVariableExpression: transform_variable_expression,
 312     }[type(expression)](accumulators, expression)
 313
 314 def transform_symbol_assignment_statement(accumulators, assignment_statement):
 315     # TODO Check that target is not a builtin
 316     try:
 317         symbol_list_index = accumulators.symbol_list.index(assignment_statement.target)
 318     except ValueError:
 319         symbol_list_index = len(accumulators.symbol_list)
 320         accumulators.symbol_list.append(assignment_statement.target)
 321
 322     return CSymbolAssignmentStatement(
 323         target=assignment_statement.target,
 324         target_symbol_list_index=symbol_list_index,
 325         expression=transform_expression(
 326             accumulators,
 327             assignment_statement.expression,
 328         ),
 329     )
 330
 331 def transform_function_call_expression(accumulators, function_call):
 332     # TODO Use the symbol from SYMBOL LIST
 333     return CFunctionCallExpression(
 334         function_expression=transform_expression(accumulators, function_call.function_expression),
 335         argument_count=function_call.argument_count,
 336         argument_items=transform_expression(accumulators, function_call.argument_items),
 337     )
 338
 339 def transform_expression_statement(accumulators, statement):
 340     return CExpressionStatement(
 341         expression=transform_expression(accumulators, statement.expression),
 342     )
 343
 344 def transform_if_else_statement(accumulators, statement):
 345     return CIfElseStatement(
 346         condition_expression=transform_expression(accumulators, statement.condition_expression),
 347         if_statement_list=tuple(transform_statement(accumulators, s) for s in statement.if_statement_list),
 348         else_statement_list=tuple(transform_statement(accumulators, s) for s in statement.else_statement_list),
 349     )
 350
 351 def transform_array_variable_initialization_statement(accumulators, statement):
 352     return CArrayVariableInitializationStatement(
 353         variable=statement.variable,
 354         items=tuple(transform_expression(accumulators, i) for i in statement.items),
 355     )
 356
 357 def transform_variable_initialization_statement(accumulators, statement):
 358     return CVariableInitializationStatement(
 359         variable=statement.variable,
 360         expression=transform_expression(accumulators, statement.expression),
 361     )
 362
 363 def transform_variable_reassignment_statement(accumulators, statement):
 364     return CVariableReassignmentStatement(
 365         variable=statement.variable,
 366         expression=transform_expression(accumulators, statement.expression),
 367     )
 368
 369 def transform_function_definition_statement(accumulators, statement):
 370     # TODO Allow defining the same function in different contexts
 371     if any(fd.name == statement.name for fd in accumulators.function_definition_list):
 372         raise Exception('A function with name "{}" already exists'.format(statement.name))
 373
 374     # TODO Add argument names to the symbol table
 375     accumulators.function_definition_list.append(CFunctionDefinition(
 376         name=statement.name,
 377         argument_name_list=statement.argument_name_list,
 378         statement_list=tuple(transform_statement(accumulators, s) for s in statement.statement_list)
 379     ))
 380
 381     return CFunctionDeclaration(name=statement.name)
 382
 383 def transform_statement(accumulators, statement):
 384     return {
 385         parsing.FurExpressionStatement: transform_expression_statement,
 386         normalization.NormalArrayVariableInitializationStatement: transform_array_variable_initialization_statement,
 387         normalization.NormalAssignmentStatement: transform_symbol_assignment_statement,
 388         normalization.NormalExpressionStatement: transform_expression_statement,
 389         normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement,
 390         normalization.NormalIfElseStatement: transform_if_else_statement,
 391         normalization.NormalListAppendStatement: transform_list_append_statement,
 392         normalization.NormalVariableInitializationStatement: transform_variable_initialization_statement,
 393         normalization.NormalVariableReassignmentStatement: transform_variable_reassignment_statement,
 394     }[type(statement)](accumulators, statement)
 395
 396
 397 Accumulators = collections.namedtuple(
 398     'Accumulators',
 399     [
 400         'builtin_set',
 401         'function_definition_list',
 402         'operator_set',
 403         'symbol_list',
 404         'string_literal_list',
 405     ],
 406 )
 407
 408 def transform(program):
 409     accumulators = Accumulators(
 410         builtin_set=set(),
 411         function_definition_list=[],
 412         operator_set=set(),
 413         symbol_list=[],
 414         string_literal_list=[],
 415     )
 416
 417     statement_list = [
 418         transform_statement(accumulators, statement) for statement in program.statement_list
 419     ]
 420
 421     # This prevents warnings about normalized variables being entire C statements
 422     last_statement = statement_list[-1]
 423     if isinstance(last_statement, normalization.NormalExpressionStatement) and isinstance(last_statement.expression, normalization.NormalVariableExpression):
 424         del statement_list[-1]
 425
 426     standard_library_set = set()
 427     for builtin in accumulators.builtin_set:
 428         for standard_library in BUILTINS[builtin]:
 429             standard_library_set.add(standard_library)
 430
 431     return CProgram(
 432         builtin_set=accumulators.builtin_set,
 433         function_definition_list=accumulators.function_definition_list,
 434         operator_declarations=tuple(sorted(accumulators.operator_set)),
 435         statements=statement_list,
 436         standard_libraries=standard_library_set,
 437         string_literal_list=accumulators.string_literal_list,
 438         symbol_list=accumulators.symbol_list,
 439     )
 440
 441
 442 if __name__ == '__main__':
 443     import unittest
 444
 445     unittest.main()