code.kerkeslager.com Git - fur/blob - normalization.py

   1 import collections
   2
   3 import parsing
   4 import util
   5
   6 NormalVariableExpression = collections.namedtuple(
   7     'NormalVariableExpression',
   8     [
   9         'variable',
  10     ],
  11 )
  12
  13 NormalIntegerLiteralExpression = collections.namedtuple(
  14     'NormalIntegerLiteralExpression',
  15     [
  16         'integer',
  17     ],
  18 )
  19
  20 NormalStringLiteralExpression = collections.namedtuple(
  21     'NormalStringLiteralExpression',
  22     [
  23         'string',
  24     ],
  25 )
  26
  27 NormalSymbolExpression = collections.namedtuple(
  28     'NormalSymbolExpression',
  29     [
  30         'symbol',
  31     ],
  32 )
  33
  34 NormalNegationExpression = collections.namedtuple(
  35     'NormalNegationExpression',
  36     [
  37         'internal_expression',
  38     ],
  39 )
  40
  41 NormalInfixExpression = collections.namedtuple(
  42     'NormalInfixExpression',
  43     [
  44         'order',
  45         'operator',
  46         'left',
  47         'right',
  48     ],
  49 )
  50
  51 NormalFunctionCallExpression = collections.namedtuple(
  52     'NormalFunctionCallExpression',
  53     [
  54         'function_expression',
  55         'argument_count',
  56         'argument_items',
  57     ],
  58 )
  59
  60 NormalArrayVariableInitializationStatement = collections.namedtuple(
  61     'NormalArrayVariableInitializationStatement',
  62     [
  63         'variable',
  64         'items',
  65     ],
  66 )
  67
  68 NormalVariableInitializationStatement = collections.namedtuple(
  69     'NormalVariableInitializationStatement',
  70     [
  71         'variable',
  72         'expression',
  73     ],
  74 )
  75
  76 NormalVariableReassignmentStatement = collections.namedtuple(
  77     'NormalVariableReassignmentStatement',
  78     [
  79         'variable',
  80         'expression',
  81     ],
  82 )
  83
  84 NormalExpressionStatement = collections.namedtuple(
  85     'NormalExpressionStatement',
  86     [
  87         'expression',
  88     ],
  89 )
  90
  91 NormalAssignmentStatement = collections.namedtuple(
  92     'NormalAssignmentStatement',
  93     [
  94         'target',
  95         'expression',
  96     ],
  97 )
  98
  99 NormalIfElseStatement = collections.namedtuple(
 100     'NormalIfElseStatement',
 101     [
 102         'condition_expression',
 103         'if_statement_list',
 104         'else_statement_list',
 105     ],
 106 )
 107
 108 NormalFunctionDefinitionStatement = collections.namedtuple(
 109     'NormalFunctionDefinitionStatement',
 110     [
 111         'name',
 112         'argument_name_list',
 113         'statement_list',
 114     ],
 115 )
 116
 117 NormalProgram = collections.namedtuple(
 118     'NormalProgram',
 119     [
 120         'statement_list',
 121     ],
 122 )
 123
 124 def fake_normalization(counter, thing):
 125     return (counter, (), thing)
 126
 127 def normalize_integer_literal_expression(counter, expression):
 128     variable = '${}'.format(counter)
 129     return (
 130         counter + 1,
 131         (
 132             NormalVariableInitializationStatement(
 133                 variable=variable,
 134                 expression=NormalIntegerLiteralExpression(integer=expression.integer),
 135             ),
 136         ),
 137         NormalVariableExpression(variable=variable),
 138     )
 139
 140 def normalize_string_literal_expression(counter, expression):
 141     variable = '${}'.format(counter)
 142     return (
 143         counter + 1,
 144         (
 145             NormalVariableInitializationStatement(
 146                 variable=variable,
 147                 expression=NormalStringLiteralExpression(string=expression.string),
 148             ),
 149         ),
 150         NormalVariableExpression(variable=variable),
 151     )
 152
 153 def normalize_symbol_expression(counter, expression):
 154     variable = '${}'.format(counter)
 155     return (
 156         counter + 1,
 157         (
 158             NormalVariableInitializationStatement(
 159                 variable=variable,
 160                 expression=NormalSymbolExpression(symbol=expression.symbol),
 161             ),
 162         ),
 163         NormalVariableExpression(variable=variable),
 164     )
 165
 166 def normalize_function_call_expression(counter, expression):
 167     assert isinstance(expression, parsing.FurFunctionCallExpression)
 168
 169     prestatements = []
 170     arguments = []
 171
 172     for argument in expression.arguments:
 173         counter, argument_prestatements, normalized_argument = normalize_expression(counter, argument)
 174
 175         for s in argument_prestatements:
 176             prestatements.append(s)
 177
 178         variable = '${}'.format(counter)
 179         prestatements.append(
 180             NormalVariableInitializationStatement(
 181                 variable=variable,
 182                 expression=normalized_argument,
 183             )
 184         )
 185         arguments.append(NormalVariableExpression(
 186             variable=variable,
 187         ))
 188         counter += 1
 189
 190     arguments_variable = '${}'.format(counter)
 191     counter += 1
 192
 193     prestatements.append(NormalArrayVariableInitializationStatement(
 194         variable=arguments_variable,
 195         items=tuple(arguments),
 196     ))
 197
 198     counter, function_prestatements, function_expression = normalize_expression(
 199         counter,
 200         expression.function,
 201     )
 202
 203     for ps in function_prestatements:
 204         prestatements.append(ps)
 205
 206     if not isinstance(function_expression, NormalVariableExpression):
 207         function_variable = '${}'.format(counter)
 208
 209         prestatements.append(
 210             NormalVariableInitializationStatement(
 211                 variable=function_variable,
 212                 expression=function_expression,
 213             )
 214         )
 215
 216         function_expression = NormalVariableExpression(variable=function_variable)
 217         counter += 1
 218
 219     return (
 220         counter,
 221         tuple(prestatements),
 222         NormalFunctionCallExpression(
 223             function_expression=function_expression,
 224             argument_count=len(arguments),
 225             argument_items=NormalVariableExpression(variable=arguments_variable),
 226         ),
 227     )
 228
 229 def normalize_basic_infix_operation(counter, expression):
 230     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 231     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 232
 233     left_variable = '${}'.format(counter)
 234     counter += 1
 235     right_variable = '${}'.format(counter)
 236     counter += 1
 237     center_variable = '${}'.format(counter)
 238     counter += 1
 239
 240     root_prestatements = (
 241         NormalVariableInitializationStatement(
 242             variable=left_variable,
 243             expression=left_expression,
 244         ),
 245         NormalVariableInitializationStatement(
 246             variable=right_variable,
 247             expression=right_expression,
 248         ),
 249         NormalVariableInitializationStatement(
 250             variable=center_variable,
 251             expression=NormalInfixExpression(
 252                 order=expression.order,
 253                 operator=expression.operator,
 254                 left=NormalVariableExpression(variable=left_variable),
 255                 right=NormalVariableExpression(variable=right_variable),
 256             ),
 257         ),
 258     )
 259
 260     return (
 261         counter,
 262         left_prestatements + right_prestatements + root_prestatements,
 263         NormalVariableExpression(variable=center_variable),
 264     )
 265
 266 def normalize_comparison_expression(counter, expression):
 267     stack = []
 268
 269     while isinstance(expression.left, parsing.FurInfixExpression) and expression.order == 'comparison_level':
 270         stack.append((expression.operator, expression.order, expression.right))
 271         expression = expression.left
 272
 273     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 274     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 275
 276     left_variable = '${}'.format(counter)
 277     counter += 1
 278     right_variable = '${}'.format(counter)
 279     counter += 1
 280
 281     root_prestatements = (
 282         NormalVariableInitializationStatement(
 283             variable=left_variable,
 284             expression=left_expression,
 285         ),
 286         NormalVariableInitializationStatement(
 287             variable=right_variable,
 288             expression=right_expression,
 289         ),
 290     )
 291
 292     counter, result_prestatements, result_expression = (
 293         counter,
 294         left_prestatements + right_prestatements + root_prestatements,
 295         NormalInfixExpression(
 296             order=expression.order,
 297             operator=expression.operator,
 298             left=NormalVariableExpression(variable=left_variable),
 299             right=NormalVariableExpression(variable=right_variable),
 300         ),
 301     )
 302
 303     while len(stack) > 0:
 304         right_operator, right_order, right_expression = stack.pop()
 305         and_right_expression = parsing.FurInfixExpression(
 306             operator=right_operator,
 307             order=right_order,
 308             left=NormalVariableExpression(variable=right_variable),
 309             right=right_expression,
 310         )
 311
 312         and_expression = parsing.FurInfixExpression(
 313             operator='and',
 314             order='and_level',
 315             left=result_expression,
 316             right=and_right_expression,
 317         )
 318
 319         counter, and_prestatements, result_expression = normalize_boolean_expression(
 320             counter,
 321             and_expression,
 322         )
 323
 324         result_prestatements = result_prestatements + and_prestatements
 325
 326     return (counter, result_prestatements, result_expression)
 327
 328 def normalize_boolean_expression(counter, expression):
 329     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 330     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 331
 332     result_variable = '${}'.format(counter)
 333     if_else_prestatment = NormalVariableInitializationStatement(
 334         variable=result_variable,
 335         expression=left_expression,
 336     )
 337     counter += 1
 338
 339     condition_expression=NormalVariableExpression(variable=result_variable)
 340     short_circuited_statements = right_prestatements + (NormalVariableReassignmentStatement(variable=result_variable, expression=right_expression),)
 341
 342     if expression.operator == 'and':
 343         if_else_statement = NormalIfElseStatement(
 344             condition_expression=condition_expression,
 345             if_statement_list=short_circuited_statements,
 346             else_statement_list=(),
 347         )
 348
 349     elif expression.operator == 'or':
 350         if_else_statement = NormalIfElseStatement(
 351             condition_expression=condition_expression,
 352             if_statement_list=(),
 353             else_statement_list=short_circuited_statements,
 354         )
 355
 356     else:
 357         raise Exception('Unable to handle operator "{}"'.format(expression.operator))
 358
 359     return (
 360         counter,
 361         left_prestatements + (if_else_prestatment, if_else_statement),
 362         NormalVariableExpression(variable=result_variable),
 363     )
 364
 365
 366 def normalize_infix_expression(counter, expression):
 367     return {
 368         'multiplication_level': normalize_basic_infix_operation,
 369         'addition_level': normalize_basic_infix_operation,
 370         'comparison_level': normalize_comparison_expression,
 371         'and_level': normalize_boolean_expression,
 372         'or_level': normalize_boolean_expression,
 373     }[expression.order](counter, expression)
 374
 375 def normalize_if_expression(counter, expression):
 376     counter, condition_prestatements, condition_expression = normalize_expression(
 377         counter,
 378         expression.condition_expression,
 379     )
 380
 381     result_variable = '${}'.format(counter)
 382     counter += 1
 383
 384     counter, if_statement_list = normalize_statement_list(
 385         counter,
 386         expression.if_statement_list,
 387         assign_result_to=result_variable,
 388     )
 389     counter, else_statement_list = normalize_statement_list(
 390         counter,
 391         expression.else_statement_list,
 392         assign_result_to=result_variable,
 393     )
 394
 395     return (
 396         counter,
 397         condition_prestatements + (
 398             NormalVariableInitializationStatement(
 399                 variable=result_variable,
 400                 expression=NormalVariableExpression(variable='builtin$nil'),
 401             ),
 402             NormalIfElseStatement(
 403                 condition_expression=condition_expression,
 404                 if_statement_list=if_statement_list,
 405                 else_statement_list=else_statement_list,
 406             ),
 407         ),
 408         NormalVariableExpression(variable=result_variable),
 409     )
 410
 411
 412
 413
 414 def normalize_negation_expression(counter, expression):
 415     counter, prestatements, internal_expression = normalize_expression(counter, expression.value)
 416
 417     internal_variable = '${}'.format(counter)
 418     counter += 1
 419
 420     return (
 421         counter,
 422         prestatements + (
 423             NormalVariableInitializationStatement(
 424                 variable=internal_variable,
 425                 expression=internal_expression,
 426             ),
 427         ),
 428         NormalNegationExpression(internal_expression=NormalVariableExpression(variable=internal_variable)),
 429     )
 430
 431 def normalize_expression(counter, expression):
 432     return {
 433         NormalInfixExpression: fake_normalization,
 434         NormalVariableExpression: fake_normalization,
 435         parsing.FurFunctionCallExpression: normalize_function_call_expression,
 436         parsing.FurIfExpression: normalize_if_expression,
 437         parsing.FurInfixExpression: normalize_infix_expression,
 438         parsing.FurIntegerLiteralExpression: normalize_integer_literal_expression,
 439         parsing.FurNegationExpression: normalize_negation_expression,
 440         parsing.FurStringLiteralExpression: normalize_string_literal_expression,
 441         parsing.FurSymbolExpression: normalize_symbol_expression,
 442     }[type(expression)](counter, expression)
 443
 444 def normalize_expression_statement(counter, statement):
 445     # TODO Normalized will be a NormalVariableExpression, which will go unused
 446     # for expression statements in every case except when it's a return
 447     # statement. This cases warnings on C compilation. We should only generate
 448     # this variable when it will be used on return.
 449     counter, prestatements, normalized = normalize_expression(counter, statement.expression)
 450
 451     return (
 452         counter,
 453         prestatements,
 454         NormalExpressionStatement(expression=normalized),
 455     )
 456
 457 def normalize_function_definition_statement(counter, statement):
 458     _, statement_list = normalize_statement_list(
 459         0,
 460         statement.statement_list,
 461         assign_result_to='result',
 462     )
 463     return (
 464         counter,
 465         (),
 466         NormalFunctionDefinitionStatement(
 467             name=statement.name,
 468             argument_name_list=statement.argument_name_list,
 469             statement_list=statement_list,
 470         ),
 471     )
 472
 473 def normalize_assignment_statement(counter, statement):
 474     counter, prestatements, normalized_expression = normalize_expression(counter, statement.expression)
 475     return (
 476         counter,
 477         prestatements,
 478         NormalAssignmentStatement(
 479             target=statement.target,
 480             expression=normalized_expression,
 481         ),
 482     )
 483
 484 def normalize_statement(counter, statement):
 485     return {
 486         parsing.FurAssignmentStatement: normalize_assignment_statement,
 487         parsing.FurExpressionStatement: normalize_expression_statement,
 488         parsing.FurFunctionDefinitionStatement: normalize_function_definition_statement,
 489     }[type(statement)](counter, statement)
 490
 491 @util.force_generator(tuple)
 492 def normalize_statement_list(counter, statement_list, **kwargs):
 493     assign_result_to = kwargs.pop('assign_result_to', None)
 494
 495     assert len(kwargs) == 0
 496
 497     result_statement_list = []
 498
 499     for statement in statement_list:
 500         counter, prestatements, normalized = normalize_statement(counter, statement)
 501         for s in prestatements:
 502             result_statement_list.append(s)
 503         result_statement_list.append(normalized)
 504
 505     last_statement = result_statement_list[-1]
 506
 507     if isinstance(last_statement, NormalExpressionStatement) and isinstance(last_statement.expression, NormalVariableExpression):
 508         result_expression = result_statement_list.pop().expression
 509
 510         if assign_result_to is not None:
 511             result_statement_list.append(
 512                 NormalVariableReassignmentStatement(
 513                     variable=assign_result_to,
 514                     expression=result_expression,
 515                 )
 516             )
 517
 518     return (
 519         counter,
 520         result_statement_list,
 521     )
 522
 523 def normalize(program):
 524     _, statement_list = normalize_statement_list(0, program.statement_list)
 525
 526     return NormalProgram(
 527         statement_list=statement_list,
 528     )