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 NormalDotExpression = collections.namedtuple(
  42     'NormalDotExpression',
  43     [
  44         'instance',
  45         'field',
  46     ],
  47 )
  48
  49 NormalInfixExpression = collections.namedtuple(
  50     'NormalInfixExpression',
  51     [
  52         'order',
  53         'operator',
  54     ],
  55 )
  56
  57 NormalPushStatement = collections.namedtuple(
  58     'NormalPushStatement',
  59     (
  60         'expression',
  61     ),
  62 )
  63
  64 NormalFunctionCallExpression = collections.namedtuple(
  65     'NormalFunctionCallExpression',
  66     [
  67         'function_expression',
  68         'argument_count',
  69     ],
  70 )
  71
  72 NormalArrayVariableInitializationStatement = collections.namedtuple(
  73     'NormalArrayVariableInitializationStatement',
  74     [
  75         'variable',
  76         'items',
  77     ],
  78 )
  79
  80 NormalSymbolArrayVariableInitializationStatement = collections.namedtuple(
  81     'NormalSymbolArrayVariableInitializationStatement',
  82     [
  83         'variable',
  84         'symbol_list',
  85     ],
  86 )
  87
  88 NormalVariableInitializationStatement = collections.namedtuple(
  89     'NormalVariableInitializationStatement',
  90     [
  91         'variable',
  92         'expression',
  93     ],
  94 )
  95
  96 NormalVariableReassignmentStatement = collections.namedtuple(
  97     'NormalVariableReassignmentStatement',
  98     [
  99         'variable',
 100         'expression',
 101     ],
 102 )
 103
 104 NormalExpressionStatement = collections.namedtuple(
 105     'NormalExpressionStatement',
 106     [
 107         'expression',
 108     ],
 109 )
 110
 111 NormalAssignmentStatement = collections.namedtuple(
 112     'NormalAssignmentStatement',
 113     [
 114         'target',
 115         'expression',
 116     ],
 117 )
 118
 119 NormalIfElseStatement = collections.namedtuple(
 120     'NormalIfElseStatement',
 121     [
 122         'condition_expression',
 123         'if_statement_list',
 124         'else_statement_list',
 125     ],
 126 )
 127
 128 NormalFunctionDefinitionStatement = collections.namedtuple(
 129     'NormalFunctionDefinitionStatement',
 130     [
 131         'name',
 132         'argument_name_list',
 133         'statement_list',
 134     ],
 135 )
 136
 137 NormalProgram = collections.namedtuple(
 138     'NormalProgram',
 139     [
 140         'statement_list',
 141     ],
 142 )
 143
 144 def fake_normalization(counter, thing):
 145     return (counter, (), thing)
 146
 147 def normalize_integer_literal_expression(counter, expression):
 148     variable = '${}'.format(counter)
 149     return (
 150         counter + 1,
 151         (
 152             NormalVariableInitializationStatement(
 153                 variable=variable,
 154                 expression=NormalIntegerLiteralExpression(integer=expression.integer),
 155             ),
 156         ),
 157         NormalVariableExpression(variable=variable),
 158     )
 159
 160 NormalListConstructExpression = collections.namedtuple(
 161     'NormalListConstructExpression',
 162     [
 163         'allocate',
 164     ],
 165 )
 166
 167 NormalListAppendStatement = collections.namedtuple(
 168     'NormalListAppendStatement',
 169     [
 170         'list_expression',
 171         'item_expression',
 172     ],
 173 )
 174
 175 NormalListGetExpression = collections.namedtuple(
 176     'NormalListGetExpression',
 177     [
 178         'list_expression',
 179         'index_expression',
 180     ],
 181 )
 182
 183 def normalize_list_literal_expression(counter, expression):
 184     list_variable = '${}'.format(counter)
 185     counter += 1
 186
 187     prestatements = [
 188         NormalVariableInitializationStatement(
 189             variable=list_variable,
 190             expression=NormalListConstructExpression(allocate=len(expression.item_expression_list)),
 191         ),
 192     ]
 193
 194     list_expression = NormalVariableExpression(variable=list_variable)
 195
 196     for item_expression in expression.item_expression_list:
 197         counter, item_expression_prestatements, normalized = normalize_expression(
 198             counter,
 199             item_expression,
 200         )
 201
 202         for p in item_expression_prestatements:
 203             prestatements.append(p)
 204
 205         prestatements.append(
 206             NormalListAppendStatement(
 207                 list_expression=list_expression,
 208                 item_expression=normalized,
 209             )
 210         )
 211
 212     return (
 213         counter,
 214         tuple(prestatements),
 215         list_expression,
 216     )
 217
 218 def normalize_list_item_expression(counter, expression):
 219     counter, list_prestatements, list_expression = normalize_expression(counter, expression.list_expression)
 220     counter, index_prestatements, index_expression = normalize_expression(counter, expression.index_expression)
 221
 222     result_variable = '${}'.format(counter)
 223     result_prestatement = NormalVariableInitializationStatement(
 224         variable=result_variable,
 225         expression=NormalListGetExpression(
 226             list_expression=list_expression,
 227             index_expression=index_expression,
 228         ),
 229     )
 230
 231     return (
 232         counter + 1,
 233         list_prestatements + index_prestatements + (result_prestatement,),
 234         NormalVariableExpression(variable=result_variable),
 235     )
 236
 237 def normalize_string_literal_expression(counter, expression):
 238     variable = '${}'.format(counter)
 239     return (
 240         counter + 1,
 241         (
 242             NormalVariableInitializationStatement(
 243                 variable=variable,
 244                 expression=NormalStringLiteralExpression(string=expression.string),
 245             ),
 246         ),
 247         NormalVariableExpression(variable=variable),
 248     )
 249
 250 NormalStructureLiteralExpression = collections.namedtuple(
 251     'NormalStructureLiteralExpression',
 252     [
 253         'field_count',
 254         'symbol_list_variable',
 255         'value_list_variable',
 256     ],
 257 )
 258
 259 def normalize_structure_literal_expression(counter, expression):
 260     prestatements = []
 261     field_symbol_array = []
 262     field_value_array = []
 263
 264     for symbol_expression_pair in expression.fields:
 265         counter, field_prestatements, field_expression = normalize_expression(
 266             counter,
 267             symbol_expression_pair.expression,
 268         )
 269
 270         for p in field_prestatements:
 271             prestatements.append(p)
 272
 273         field_symbol_array.append(symbol_expression_pair.symbol)
 274         field_value_array.append(field_expression)
 275
 276     symbol_array_variable = '${}'.format(counter)
 277     counter += 1
 278
 279     prestatements.append(
 280         NormalSymbolArrayVariableInitializationStatement(
 281             variable=symbol_array_variable,
 282             symbol_list=tuple(field_symbol_array),
 283         )
 284     )
 285
 286     value_array_variable = '${}'.format(counter)
 287     counter += 1
 288
 289     prestatements.append(
 290         NormalArrayVariableInitializationStatement(
 291             variable=value_array_variable,
 292             items=tuple(field_value_array),
 293         )
 294     )
 295
 296     variable = '${}'.format(counter)
 297
 298     prestatements.append(
 299         NormalVariableInitializationStatement(
 300             variable=variable,
 301             expression=NormalStructureLiteralExpression(
 302                 field_count=len(expression.fields),
 303                 symbol_list_variable=symbol_array_variable,
 304                 value_list_variable=value_array_variable,
 305             ),
 306         )
 307     )
 308
 309     return (
 310         counter + 1,
 311         tuple(prestatements),
 312         NormalVariableExpression(variable=variable),
 313     )
 314
 315
 316 def normalize_symbol_expression(counter, expression):
 317     variable = '${}'.format(counter)
 318     return (
 319         counter + 1,
 320         (
 321             NormalVariableInitializationStatement(
 322                 variable=variable,
 323                 expression=NormalSymbolExpression(symbol=expression.symbol),
 324             ),
 325         ),
 326         NormalVariableExpression(variable=variable),
 327     )
 328
 329 def normalize_function_call_expression(counter, expression):
 330     assert isinstance(expression, parsing.FurFunctionCallExpression)
 331
 332     prestatements = []
 333
 334     for argument in expression.arguments:
 335         counter, argument_prestatements, normalized_argument = normalize_expression(counter, argument)
 336
 337         for s in argument_prestatements:
 338             prestatements.append(s)
 339
 340         variable = '${}'.format(counter)
 341         prestatements.append(
 342             NormalVariableInitializationStatement(
 343                 variable=variable,
 344                 expression=normalized_argument,
 345             )
 346         )
 347         prestatements.append(
 348             NormalPushStatement(
 349                 expression=NormalVariableExpression(
 350                     variable=variable,
 351                 ),
 352             ),
 353         )
 354         counter += 1
 355
 356     counter, function_prestatements, function_expression = normalize_expression(
 357         counter,
 358         expression.function,
 359     )
 360
 361     for ps in function_prestatements:
 362         prestatements.append(ps)
 363
 364     if not isinstance(function_expression, NormalVariableExpression):
 365         function_variable = '${}'.format(counter)
 366
 367         prestatements.append(
 368             NormalVariableInitializationStatement(
 369                 variable=function_variable,
 370                 expression=function_expression,
 371             )
 372         )
 373
 374         function_expression = NormalVariableExpression(variable=function_variable)
 375         counter += 1
 376
 377     result_variable = '${}'.format(counter)
 378
 379     prestatements.append(
 380         NormalVariableInitializationStatement(
 381             variable=result_variable,
 382             expression=NormalFunctionCallExpression(
 383                 function_expression=function_expression,
 384                 argument_count=len(expression.arguments),
 385             ),
 386         )
 387     )
 388
 389     return (
 390         counter + 1,
 391         tuple(prestatements),
 392         NormalVariableExpression(variable=result_variable),
 393     )
 394
 395 def normalize_basic_infix_operation(counter, expression):
 396     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 397     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 398
 399     center_variable = '${}'.format(counter)
 400     counter += 1
 401
 402     root_prestatements = (
 403         NormalPushStatement(expression=left_expression),
 404         NormalPushStatement(expression=right_expression),
 405         NormalVariableInitializationStatement(
 406             variable=center_variable,
 407             expression=NormalInfixExpression(
 408                 order=expression.order,
 409                 operator=expression.operator,
 410             ),
 411         ),
 412     )
 413
 414     return (
 415         counter,
 416         left_prestatements + right_prestatements + root_prestatements,
 417         NormalVariableExpression(variable=center_variable),
 418     )
 419
 420 def desugar_ternary_comparison(counter, expression):
 421     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left.left)
 422     counter, middle_prestatements, middle_expression = normalize_expression(counter, expression.left.right)
 423
 424     left_variable = '${}'.format(counter)
 425     counter += 1
 426     middle_variable = '${}'.format(counter)
 427     counter += 1
 428
 429     # TODO Is there a memory leak if the middle expression throws an exception because the first expression result hasn't been added to the stack?
 430     juncture_prestatements = (
 431         NormalVariableInitializationStatement(
 432             variable=left_variable,
 433             expression=left_expression,
 434         ),
 435         NormalVariableInitializationStatement(
 436             variable=middle_variable,
 437             expression=middle_expression,
 438         )
 439     )
 440
 441     counter, boolean_expression_prestatements, boolean_expression =  normalize_boolean_expression(
 442         counter,
 443         parsing.FurInfixExpression(
 444             order='and_level',
 445             operator='and',
 446             left=parsing.FurInfixExpression(
 447                 order='comparison_level',
 448                 operator=expression.left.operator,
 449                 left=NormalVariableExpression(variable=left_variable),
 450                 right=NormalVariableExpression(variable=middle_variable),
 451             ),
 452             right=parsing.FurInfixExpression(
 453                 order='comparison_level',
 454                 operator=expression.operator,
 455                 left=NormalVariableExpression(variable=middle_variable),
 456                 right=expression.right,
 457             ),
 458         )
 459     )
 460
 461     return (
 462         counter,
 463         left_prestatements + middle_prestatements + juncture_prestatements + boolean_expression_prestatements,
 464         boolean_expression,
 465     )
 466
 467 def normalize_comparison_expression(counter, expression):
 468     if isinstance(expression.left, parsing.FurInfixExpression) and expression.order == 'comparison_level':
 469         return desugar_ternary_comparison(counter, expression)
 470
 471     return normalize_basic_infix_operation(counter, expression)
 472
 473 def normalize_boolean_expression(counter, expression):
 474     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 475     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 476
 477     result_variable = '${}'.format(counter)
 478     if_else_prestatment = NormalVariableInitializationStatement(
 479         variable=result_variable,
 480         expression=left_expression,
 481     )
 482     counter += 1
 483
 484     condition_expression=NormalVariableExpression(variable=result_variable)
 485     short_circuited_statements = right_prestatements + (NormalVariableReassignmentStatement(variable=result_variable, expression=right_expression),)
 486
 487     if expression.operator == 'and':
 488         if_else_statement = NormalIfElseStatement(
 489             condition_expression=condition_expression,
 490             if_statement_list=short_circuited_statements,
 491             else_statement_list=(),
 492         )
 493
 494     elif expression.operator == 'or':
 495         if_else_statement = NormalIfElseStatement(
 496             condition_expression=condition_expression,
 497             if_statement_list=(),
 498             else_statement_list=short_circuited_statements,
 499         )
 500
 501     else:
 502         raise Exception('Unable to handle operator "{}"'.format(expression.operator))
 503
 504     return (
 505         counter,
 506         left_prestatements + (if_else_prestatment, if_else_statement),
 507         NormalVariableExpression(variable=result_variable),
 508     )
 509
 510 def normalize_dot_expression(counter, expression):
 511     assert isinstance(expression.right, parsing.FurSymbolExpression)
 512
 513     counter, prestatements, left_expression = normalize_expression(counter, expression.left)
 514
 515     variable = '${}'.format(counter)
 516
 517     dot_expression_prestatement = NormalVariableInitializationStatement(
 518         variable=variable,
 519         expression=NormalDotExpression(
 520             instance=left_expression,
 521             field=expression.right.symbol,
 522         ),
 523     )
 524
 525     return (
 526         counter + 1,
 527         prestatements + (dot_expression_prestatement,),
 528         NormalVariableExpression(variable=variable),
 529     )
 530
 531 def normalize_infix_expression(counter, expression):
 532     return {
 533         'multiplication_level': normalize_basic_infix_operation,
 534         'addition_level': normalize_basic_infix_operation,
 535         'comparison_level': normalize_comparison_expression,
 536         'dot_level': normalize_dot_expression,
 537         'and_level': normalize_boolean_expression,
 538         'or_level': normalize_boolean_expression,
 539     }[expression.order](counter, expression)
 540
 541 def normalize_if_expression(counter, expression):
 542     counter, condition_prestatements, condition_expression = normalize_expression(
 543         counter,
 544         expression.condition_expression,
 545     )
 546
 547     result_variable = '${}'.format(counter)
 548     counter += 1
 549
 550     counter, if_statement_list = normalize_statement_list(
 551         counter,
 552         expression.if_statement_list,
 553         assign_result_to=result_variable,
 554     )
 555     counter, else_statement_list = normalize_statement_list(
 556         counter,
 557         expression.else_statement_list,
 558         assign_result_to=result_variable,
 559     )
 560
 561     return (
 562         counter,
 563         condition_prestatements + (
 564             NormalVariableInitializationStatement(
 565                 variable=result_variable,
 566                 expression=NormalVariableExpression(variable='builtin$nil'),
 567             ),
 568             NormalIfElseStatement(
 569                 condition_expression=condition_expression,
 570                 if_statement_list=if_statement_list,
 571                 else_statement_list=else_statement_list,
 572             ),
 573         ),
 574         NormalVariableExpression(variable=result_variable),
 575     )
 576
 577 def normalize_negation_expression(counter, expression):
 578     counter, prestatements, internal_expression = normalize_expression(counter, expression.value)
 579
 580     internal_variable = '${}'.format(counter)
 581     counter += 1
 582
 583     return (
 584         counter,
 585         prestatements + (
 586             NormalVariableInitializationStatement(
 587                 variable=internal_variable,
 588                 expression=internal_expression,
 589             ),
 590         ),
 591         NormalNegationExpression(internal_expression=NormalVariableExpression(variable=internal_variable)),
 592     )
 593
 594 def normalize_expression(counter, expression):
 595     return {
 596         NormalInfixExpression: fake_normalization,
 597         NormalVariableExpression: fake_normalization,
 598         parsing.FurFunctionCallExpression: normalize_function_call_expression,
 599         parsing.FurIfExpression: normalize_if_expression,
 600         parsing.FurInfixExpression: normalize_infix_expression,
 601         parsing.FurIntegerLiteralExpression: normalize_integer_literal_expression,
 602         parsing.FurListLiteralExpression: normalize_list_literal_expression,
 603         parsing.FurListItemExpression: normalize_list_item_expression,
 604         parsing.FurNegationExpression: normalize_negation_expression,
 605         parsing.FurStringLiteralExpression: normalize_string_literal_expression,
 606         parsing.FurStructureLiteralExpression: normalize_structure_literal_expression,
 607         parsing.FurSymbolExpression: normalize_symbol_expression,
 608     }[type(expression)](counter, expression)
 609
 610 def normalize_expression_statement(counter, statement):
 611     # TODO Normalized will be a NormalVariableExpression, which will go unused
 612     # for expression statements in every case except when it's a return
 613     # statement. This cases warnings on C compilation. We should only generate
 614     # this variable when it will be used on return.
 615     counter, prestatements, normalized = normalize_expression(counter, statement.expression)
 616
 617     return (
 618         counter,
 619         prestatements,
 620         NormalExpressionStatement(expression=normalized),
 621     )
 622
 623 def normalize_function_definition_statement(counter, statement):
 624     _, statement_list = normalize_statement_list(
 625         0,
 626         statement.statement_list,
 627         assign_result_to='result',
 628     )
 629     return (
 630         counter,
 631         (),
 632         NormalFunctionDefinitionStatement(
 633             name=statement.name,
 634             argument_name_list=statement.argument_name_list,
 635             statement_list=statement_list,
 636         ),
 637     )
 638
 639 def normalize_assignment_statement(counter, statement):
 640     counter, prestatements, normalized_expression = normalize_expression(counter, statement.expression)
 641     return (
 642         counter,
 643         prestatements,
 644         NormalAssignmentStatement(
 645             target=statement.target,
 646             expression=normalized_expression,
 647         ),
 648     )
 649
 650 def normalize_statement(counter, statement):
 651     return {
 652         parsing.FurAssignmentStatement: normalize_assignment_statement,
 653         parsing.FurExpressionStatement: normalize_expression_statement,
 654         parsing.FurFunctionDefinitionStatement: normalize_function_definition_statement,
 655     }[type(statement)](counter, statement)
 656
 657 @util.force_generator(tuple)
 658 def normalize_statement_list(counter, statement_list, **kwargs):
 659     assign_result_to = kwargs.pop('assign_result_to', None)
 660
 661     assert len(kwargs) == 0
 662
 663     result_statement_list = []
 664
 665     for statement in statement_list:
 666         counter, prestatements, normalized = normalize_statement(counter, statement)
 667         for s in prestatements:
 668             result_statement_list.append(s)
 669         result_statement_list.append(normalized)
 670
 671     # TODO The way we fix the last statement is really confusing
 672     last_statement = result_statement_list[-1]
 673
 674     if isinstance(last_statement, NormalExpressionStatement) and isinstance(last_statement.expression, NormalVariableExpression):
 675         if assign_result_to is not None:
 676             result_expression = result_statement_list.pop().expression
 677             result_statement_list.append(
 678                 NormalVariableReassignmentStatement(
 679                     variable=assign_result_to,
 680                     expression=result_expression,
 681                 )
 682             )
 683
 684     return (
 685         counter,
 686         result_statement_list,
 687     )
 688
 689 def normalize(program):
 690     _, statement_list = normalize_statement_list(0, program.statement_list)
 691
 692     return NormalProgram(
 693         statement_list=statement_list,
 694     )