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 NormalPushStatement = collections.namedtuple(
  60     'NormalPushStatement',
  61     (
  62         'expression',
  63     ),
  64 )
  65
  66 NormalFunctionCallExpression = collections.namedtuple(
  67     'NormalFunctionCallExpression',
  68     [
  69         'function_expression',
  70         'argument_count',
  71     ],
  72 )
  73
  74 NormalArrayVariableInitializationStatement = collections.namedtuple(
  75     'NormalArrayVariableInitializationStatement',
  76     [
  77         'variable',
  78         'items',
  79     ],
  80 )
  81
  82 NormalSymbolArrayVariableInitializationStatement = collections.namedtuple(
  83     'NormalSymbolArrayVariableInitializationStatement',
  84     [
  85         'variable',
  86         'symbol_list',
  87     ],
  88 )
  89
  90 NormalVariableInitializationStatement = collections.namedtuple(
  91     'NormalVariableInitializationStatement',
  92     [
  93         'variable',
  94         'expression',
  95     ],
  96 )
  97
  98 NormalVariableReassignmentStatement = collections.namedtuple(
  99     'NormalVariableReassignmentStatement',
 100     [
 101         'variable',
 102         'expression',
 103     ],
 104 )
 105
 106 NormalExpressionStatement = collections.namedtuple(
 107     'NormalExpressionStatement',
 108     [
 109         'expression',
 110     ],
 111 )
 112
 113 NormalAssignmentStatement = collections.namedtuple(
 114     'NormalAssignmentStatement',
 115     [
 116         'target',
 117         'expression',
 118     ],
 119 )
 120
 121 NormalIfElseStatement = collections.namedtuple(
 122     'NormalIfElseStatement',
 123     [
 124         'condition_expression',
 125         'if_statement_list',
 126         'else_statement_list',
 127     ],
 128 )
 129
 130 NormalFunctionDefinitionStatement = collections.namedtuple(
 131     'NormalFunctionDefinitionStatement',
 132     [
 133         'name',
 134         'argument_name_list',
 135         'statement_list',
 136     ],
 137 )
 138
 139 NormalProgram = collections.namedtuple(
 140     'NormalProgram',
 141     [
 142         'statement_list',
 143     ],
 144 )
 145
 146 def fake_normalization(counter, thing):
 147     return (counter, (), thing)
 148
 149 def normalize_integer_literal_expression(counter, expression):
 150     variable = '${}'.format(counter)
 151     return (
 152         counter + 1,
 153         (
 154             NormalVariableInitializationStatement(
 155                 variable=variable,
 156                 expression=NormalIntegerLiteralExpression(integer=expression.integer),
 157             ),
 158         ),
 159         NormalVariableExpression(variable=variable),
 160     )
 161
 162 NormalListConstructExpression = collections.namedtuple(
 163     'NormalListConstructExpression',
 164     [
 165         'allocate',
 166     ],
 167 )
 168
 169 NormalListAppendStatement = collections.namedtuple(
 170     'NormalListAppendStatement',
 171     [
 172         'list_expression',
 173         'item_expression',
 174     ],
 175 )
 176
 177 NormalListGetExpression = collections.namedtuple(
 178     'NormalListGetExpression',
 179     [
 180         'list_expression',
 181         'index_expression',
 182     ],
 183 )
 184
 185 def normalize_list_literal_expression(counter, expression):
 186     list_variable = '${}'.format(counter)
 187     counter += 1
 188
 189     prestatements = [
 190         NormalVariableInitializationStatement(
 191             variable=list_variable,
 192             expression=NormalListConstructExpression(allocate=len(expression.item_expression_list)),
 193         ),
 194     ]
 195
 196     list_expression = NormalVariableExpression(variable=list_variable)
 197
 198     for item_expression in expression.item_expression_list:
 199         counter, item_expression_prestatements, normalized = normalize_expression(
 200             counter,
 201             item_expression,
 202         )
 203
 204         for p in item_expression_prestatements:
 205             prestatements.append(p)
 206
 207         prestatements.append(
 208             NormalListAppendStatement(
 209                 list_expression=list_expression,
 210                 item_expression=normalized,
 211             )
 212         )
 213
 214     return (
 215         counter,
 216         tuple(prestatements),
 217         list_expression,
 218     )
 219
 220 def normalize_list_item_expression(counter, expression):
 221     counter, list_prestatements, list_expression = normalize_expression(counter, expression.list_expression)
 222     counter, index_prestatements, index_expression = normalize_expression(counter, expression.index_expression)
 223
 224     result_variable = '${}'.format(counter)
 225     result_prestatement = NormalVariableInitializationStatement(
 226         variable=result_variable,
 227         expression=NormalListGetExpression(
 228             list_expression=list_expression,
 229             index_expression=index_expression,
 230         ),
 231     )
 232
 233     return (
 234         counter + 1,
 235         list_prestatements + index_prestatements + (result_prestatement,),
 236         NormalVariableExpression(variable=result_variable),
 237     )
 238
 239 def normalize_string_literal_expression(counter, expression):
 240     variable = '${}'.format(counter)
 241     return (
 242         counter + 1,
 243         (
 244             NormalVariableInitializationStatement(
 245                 variable=variable,
 246                 expression=NormalStringLiteralExpression(string=expression.string),
 247             ),
 248         ),
 249         NormalVariableExpression(variable=variable),
 250     )
 251
 252 NormalStructureLiteralExpression = collections.namedtuple(
 253     'NormalStructureLiteralExpression',
 254     [
 255         'field_count',
 256         'symbol_list_variable',
 257         'value_list_variable',
 258     ],
 259 )
 260
 261 def normalize_structure_literal_expression(counter, expression):
 262     prestatements = []
 263     field_symbol_array = []
 264     field_value_array = []
 265
 266     for symbol_expression_pair in expression.fields:
 267         counter, field_prestatements, field_expression = normalize_expression(
 268             counter,
 269             symbol_expression_pair.expression,
 270         )
 271
 272         for p in field_prestatements:
 273             prestatements.append(p)
 274
 275         field_symbol_array.append(symbol_expression_pair.symbol)
 276         field_value_array.append(field_expression)
 277
 278     symbol_array_variable = '${}'.format(counter)
 279     counter += 1
 280
 281     prestatements.append(
 282         NormalSymbolArrayVariableInitializationStatement(
 283             variable=symbol_array_variable,
 284             symbol_list=tuple(field_symbol_array),
 285         )
 286     )
 287
 288     value_array_variable = '${}'.format(counter)
 289     counter += 1
 290
 291     prestatements.append(
 292         NormalArrayVariableInitializationStatement(
 293             variable=value_array_variable,
 294             items=tuple(field_value_array),
 295         )
 296     )
 297
 298     variable = '${}'.format(counter)
 299
 300     prestatements.append(
 301         NormalVariableInitializationStatement(
 302             variable=variable,
 303             expression=NormalStructureLiteralExpression(
 304                 field_count=len(expression.fields),
 305                 symbol_list_variable=symbol_array_variable,
 306                 value_list_variable=value_array_variable,
 307             ),
 308         )
 309     )
 310
 311     return (
 312         counter + 1,
 313         tuple(prestatements),
 314         NormalVariableExpression(variable=variable),
 315     )
 316
 317
 318 def normalize_symbol_expression(counter, expression):
 319     variable = '${}'.format(counter)
 320     return (
 321         counter + 1,
 322         (
 323             NormalVariableInitializationStatement(
 324                 variable=variable,
 325                 expression=NormalSymbolExpression(symbol=expression.symbol),
 326             ),
 327         ),
 328         NormalVariableExpression(variable=variable),
 329     )
 330
 331 def normalize_function_call_expression(counter, expression):
 332     assert isinstance(expression, parsing.FurFunctionCallExpression)
 333
 334     prestatements = []
 335
 336     for argument in expression.arguments:
 337         counter, argument_prestatements, normalized_argument = normalize_expression(counter, argument)
 338
 339         for s in argument_prestatements:
 340             prestatements.append(s)
 341
 342         variable = '${}'.format(counter)
 343         prestatements.append(
 344             NormalVariableInitializationStatement(
 345                 variable=variable,
 346                 expression=normalized_argument,
 347             )
 348         )
 349         prestatements.append(
 350             NormalPushStatement(
 351                 expression=NormalVariableExpression(
 352                     variable=variable,
 353                 ),
 354             ),
 355         )
 356         counter += 1
 357
 358     counter, function_prestatements, function_expression = normalize_expression(
 359         counter,
 360         expression.function,
 361     )
 362
 363     for ps in function_prestatements:
 364         prestatements.append(ps)
 365
 366     if not isinstance(function_expression, NormalVariableExpression):
 367         function_variable = '${}'.format(counter)
 368
 369         prestatements.append(
 370             NormalVariableInitializationStatement(
 371                 variable=function_variable,
 372                 expression=function_expression,
 373             )
 374         )
 375
 376         function_expression = NormalVariableExpression(variable=function_variable)
 377         counter += 1
 378
 379     result_variable = '${}'.format(counter)
 380
 381     prestatements.append(
 382         NormalVariableInitializationStatement(
 383             variable=result_variable,
 384             expression=NormalFunctionCallExpression(
 385                 function_expression=function_expression,
 386                 argument_count=len(expression.arguments),
 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     )