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 def transform_expression(accumulators, expression):
 259     # TODO Clean up handlers for parsing expressions
 260     return {
 261         parsing.FurInfixExpression: transform_infix_expression,
 262         parsing.FurIntegerLiteralExpression: transform_integer_literal_expression,
 263         parsing.FurNegationExpression: transform_negation_expression,
 264         parsing.FurStringLiteralExpression: transform_string_literal_expression,
 265         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 266         normalization.NormalInfixExpression: transform_infix_expression,
 267         normalization.NormalIntegerLiteralExpression: transform_integer_literal_expression,
 268         normalization.NormalNegationExpression: transform_negation_expression,
 269         normalization.NormalStringLiteralExpression: transform_string_literal_expression,
 270         normalization.NormalSymbolExpression: transform_symbol_expression,
 271         normalization.NormalVariableExpression: transform_variable_expression,
 272     }[type(expression)](accumulators, expression)
 273
 274 def transform_symbol_assignment_statement(accumulators, assignment_statement):
 275     # TODO Check that target is not a builtin
 276     try:
 277         symbol_list_index = accumulators.symbol_list.index(assignment_statement.target)
 278     except ValueError:
 279         symbol_list_index = len(accumulators.symbol_list)
 280         accumulators.symbol_list.append(assignment_statement.target)
 281
 282     return CSymbolAssignmentStatement(
 283         target=assignment_statement.target,
 284         target_symbol_list_index=symbol_list_index,
 285         expression=transform_expression(
 286             accumulators,
 287             assignment_statement.expression,
 288         ),
 289     )
 290
 291 def transform_function_call_expression(accumulators, function_call):
 292     # TODO Use the symbol from SYMBOL LIST
 293     return CFunctionCallExpression(
 294         function_expression=transform_expression(accumulators, function_call.function_expression),
 295         argument_count=function_call.argument_count,
 296         argument_items=transform_expression(accumulators, function_call.argument_items),
 297     )
 298
 299 def transform_expression_statement(accumulators, statement):
 300     return CExpressionStatement(
 301         expression=transform_expression(accumulators, statement.expression),
 302     )
 303
 304 def transform_if_else_statement(accumulators, statement):
 305     return CIfElseStatement(
 306         condition_expression=transform_expression(accumulators, statement.condition_expression),
 307         if_statement_list=tuple(transform_statement(accumulators, s) for s in statement.if_statement_list),
 308         else_statement_list=tuple(transform_statement(accumulators, s) for s in statement.else_statement_list),
 309     )
 310
 311 def transform_array_variable_initialization_statement(accumulators, statement):
 312     return CArrayVariableInitializationStatement(
 313         variable=statement.variable,
 314         items=tuple(transform_expression(accumulators, i) for i in statement.items),
 315     )
 316
 317 def transform_variable_initialization_statement(accumulators, statement):
 318     return CVariableInitializationStatement(
 319         variable=statement.variable,
 320         expression=transform_expression(accumulators, statement.expression),
 321     )
 322
 323 def transform_variable_reassignment_statement(accumulators, statement):
 324     return CVariableReassignmentStatement(
 325         variable=statement.variable,
 326         expression=transform_expression(accumulators, statement.expression),
 327     )
 328
 329 def transform_function_definition_statement(accumulators, statement):
 330     # TODO Allow defining the same function in different contexts
 331     if any(fd.name == statement.name for fd in accumulators.function_definition_list):
 332         raise Exception('A function with name "{}" already exists'.format(statement.name))
 333
 334     # TODO Add argument names to the symbol table
 335     accumulators.function_definition_list.append(CFunctionDefinition(
 336         name=statement.name,
 337         argument_name_list=statement.argument_name_list,
 338         statement_list=tuple(transform_statement(accumulators, s) for s in statement.statement_list)
 339     ))
 340
 341     return CFunctionDeclaration(name=statement.name)
 342
 343 def transform_statement(accumulators, statement):
 344     return {
 345         parsing.FurExpressionStatement: transform_expression_statement,
 346         normalization.NormalArrayVariableInitializationStatement: transform_array_variable_initialization_statement,
 347         normalization.NormalAssignmentStatement: transform_symbol_assignment_statement,
 348         normalization.NormalExpressionStatement: transform_expression_statement,
 349         normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement,
 350         normalization.NormalIfElseStatement: transform_if_else_statement,
 351         normalization.NormalVariableInitializationStatement: transform_variable_initialization_statement,
 352         normalization.NormalVariableReassignmentStatement: transform_variable_reassignment_statement,
 353     }[type(statement)](accumulators, statement)
 354
 355
 356 Accumulators = collections.namedtuple(
 357     'Accumulators',
 358     [
 359         'builtin_set',
 360         'function_definition_list',
 361         'operator_set',
 362         'symbol_list',
 363         'string_literal_list',
 364     ],
 365 )
 366
 367 def transform(program):
 368     accumulators = Accumulators(
 369         builtin_set=set(),
 370         function_definition_list=[],
 371         operator_set=set(),
 372         symbol_list=[],
 373         string_literal_list=[],
 374     )
 375
 376     statement_list = [
 377         transform_statement(accumulators, statement) for statement in program.statement_list
 378     ]
 379
 380     # This prevents warnings about normalized variables being entire C statements
 381     last_statement = statement_list[-1]
 382     if isinstance(last_statement, normalization.NormalExpressionStatement) and isinstance(last_statement.expression, normalization.NormalVariableExpression):
 383         del statement_list[-1]
 384
 385     standard_library_set = set()
 386     for builtin in accumulators.builtin_set:
 387         for standard_library in BUILTINS[builtin]:
 388             standard_library_set.add(standard_library)
 389
 390     return CProgram(
 391         builtin_set=accumulators.builtin_set,
 392         function_definition_list=accumulators.function_definition_list,
 393         operator_declarations=tuple(sorted(accumulators.operator_set)),
 394         statements=statement_list,
 395         standard_libraries=standard_library_set,
 396         string_literal_list=accumulators.string_literal_list,
 397         symbol_list=accumulators.symbol_list,
 398     )
 399
 400
 401 if __name__ == '__main__':
 402     import unittest
 403
 404     unittest.main()