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