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