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 NormalListConstructExpression = collections.namedtuple(
 141     'NormalListConstructExpression',
 142     [
 143         'allocate',
 144     ],
 145 )
 146
 147 NormalListAppendStatement = collections.namedtuple(
 148     'NormalListAppendStatement',
 149     [
 150         'list_expression',
 151         'item_expression',
 152     ],
 153 )
 154
 155 NormalListGetExpression = collections.namedtuple(
 156     'NormalListGetExpression',
 157     [
 158         'list_expression',
 159         'index_expression',
 160     ],
 161 )
 162
 163 def normalize_list_literal_expression(counter, expression):
 164     list_variable = '${}'.format(counter)
 165     counter += 1
 166
 167     prestatements = [
 168         NormalVariableInitializationStatement(
 169             variable=list_variable,
 170             expression=NormalListConstructExpression(allocate=len(expression.item_expression_list)),
 171         ),
 172     ]
 173
 174     list_expression = NormalVariableExpression(variable=list_variable)
 175
 176     for item_expression in expression.item_expression_list:
 177         counter, item_expression_prestatements, normalized = normalize_expression(
 178             counter,
 179             item_expression,
 180         )
 181
 182         for p in item_expression_prestatements:
 183             prestatements.append(p)
 184
 185         prestatements.append(
 186             NormalListAppendStatement(
 187                 list_expression=list_expression,
 188                 item_expression=normalized,
 189             )
 190         )
 191
 192     return (
 193         counter,
 194         tuple(prestatements),
 195         list_expression,
 196     )
 197
 198 def normalize_list_item_expression(counter, expression):
 199     counter, list_prestatements, list_expression = normalize_expression(counter, expression.list_expression)
 200     counter, index_prestatements, index_expression = normalize_expression(counter, expression.index_expression)
 201
 202     result_variable = '${}'.format(counter)
 203     result_prestatement = NormalVariableInitializationStatement(
 204         variable=result_variable,
 205         expression=NormalListGetExpression(
 206             list_expression=list_expression,
 207             index_expression=index_expression,
 208         ),
 209     )
 210
 211     return (
 212         counter + 1,
 213         list_prestatements + index_prestatements + (result_prestatement,),
 214         NormalVariableExpression(variable=result_variable),
 215     )
 216
 217 def normalize_string_literal_expression(counter, expression):
 218     variable = '${}'.format(counter)
 219     return (
 220         counter + 1,
 221         (
 222             NormalVariableInitializationStatement(
 223                 variable=variable,
 224                 expression=NormalStringLiteralExpression(string=expression.string),
 225             ),
 226         ),
 227         NormalVariableExpression(variable=variable),
 228     )
 229
 230 def normalize_symbol_expression(counter, expression):
 231     variable = '${}'.format(counter)
 232     return (
 233         counter + 1,
 234         (
 235             NormalVariableInitializationStatement(
 236                 variable=variable,
 237                 expression=NormalSymbolExpression(symbol=expression.symbol),
 238             ),
 239         ),
 240         NormalVariableExpression(variable=variable),
 241     )
 242
 243 def normalize_function_call_expression(counter, expression):
 244     assert isinstance(expression, parsing.FurFunctionCallExpression)
 245
 246     prestatements = []
 247     arguments = []
 248
 249     for argument in expression.arguments:
 250         counter, argument_prestatements, normalized_argument = normalize_expression(counter, argument)
 251
 252         for s in argument_prestatements:
 253             prestatements.append(s)
 254
 255         variable = '${}'.format(counter)
 256         prestatements.append(
 257             NormalVariableInitializationStatement(
 258                 variable=variable,
 259                 expression=normalized_argument,
 260             )
 261         )
 262         arguments.append(NormalVariableExpression(
 263             variable=variable,
 264         ))
 265         counter += 1
 266
 267     arguments_variable = '${}'.format(counter)
 268     counter += 1
 269
 270     prestatements.append(NormalArrayVariableInitializationStatement(
 271         variable=arguments_variable,
 272         items=tuple(arguments),
 273     ))
 274
 275     counter, function_prestatements, function_expression = normalize_expression(
 276         counter,
 277         expression.function,
 278     )
 279
 280     for ps in function_prestatements:
 281         prestatements.append(ps)
 282
 283     if not isinstance(function_expression, NormalVariableExpression):
 284         function_variable = '${}'.format(counter)
 285
 286         prestatements.append(
 287             NormalVariableInitializationStatement(
 288                 variable=function_variable,
 289                 expression=function_expression,
 290             )
 291         )
 292
 293         function_expression = NormalVariableExpression(variable=function_variable)
 294         counter += 1
 295
 296     result_variable = '${}'.format(counter)
 297
 298     prestatements.append(
 299         NormalVariableInitializationStatement(
 300             variable=result_variable,
 301             expression=NormalFunctionCallExpression(
 302                 function_expression=function_expression,
 303                 argument_count=len(arguments),
 304                 argument_items=NormalVariableExpression(variable=arguments_variable),
 305             ),
 306         )
 307     )
 308
 309     return (
 310         counter + 1,
 311         tuple(prestatements),
 312         NormalVariableExpression(variable=result_variable),
 313     )
 314
 315 def normalize_basic_infix_operation(counter, expression):
 316     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 317     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 318
 319     left_variable = '${}'.format(counter)
 320     counter += 1
 321     right_variable = '${}'.format(counter)
 322     counter += 1
 323     center_variable = '${}'.format(counter)
 324     counter += 1
 325
 326     root_prestatements = (
 327         NormalVariableInitializationStatement(
 328             variable=left_variable,
 329             expression=left_expression,
 330         ),
 331         NormalVariableInitializationStatement(
 332             variable=right_variable,
 333             expression=right_expression,
 334         ),
 335         NormalVariableInitializationStatement(
 336             variable=center_variable,
 337             expression=NormalInfixExpression(
 338                 order=expression.order,
 339                 operator=expression.operator,
 340                 left=NormalVariableExpression(variable=left_variable),
 341                 right=NormalVariableExpression(variable=right_variable),
 342             ),
 343         ),
 344     )
 345
 346     return (
 347         counter,
 348         left_prestatements + right_prestatements + root_prestatements,
 349         NormalVariableExpression(variable=center_variable),
 350     )
 351
 352 def normalize_comparison_expression(counter, expression):
 353     stack = []
 354
 355     while isinstance(expression.left, parsing.FurInfixExpression) and expression.order == 'comparison_level':
 356         stack.append((expression.operator, expression.order, expression.right))
 357         expression = expression.left
 358
 359     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 360     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 361
 362     left_variable = '${}'.format(counter)
 363     counter += 1
 364     right_variable = '${}'.format(counter)
 365     counter += 1
 366
 367     root_prestatements = (
 368         NormalVariableInitializationStatement(
 369             variable=left_variable,
 370             expression=left_expression,
 371         ),
 372         NormalVariableInitializationStatement(
 373             variable=right_variable,
 374             expression=right_expression,
 375         ),
 376     )
 377
 378     counter, result_prestatements, result_expression = (
 379         counter,
 380         left_prestatements + right_prestatements + root_prestatements,
 381         NormalInfixExpression(
 382             order=expression.order,
 383             operator=expression.operator,
 384             left=NormalVariableExpression(variable=left_variable),
 385             right=NormalVariableExpression(variable=right_variable),
 386         ),
 387     )
 388
 389     while len(stack) > 0:
 390         right_operator, right_order, right_expression = stack.pop()
 391         and_right_expression = parsing.FurInfixExpression(
 392             operator=right_operator,
 393             order=right_order,
 394             left=NormalVariableExpression(variable=right_variable),
 395             right=right_expression,
 396         )
 397
 398         and_expression = parsing.FurInfixExpression(
 399             operator='and',
 400             order='and_level',
 401             left=result_expression,
 402             right=and_right_expression,
 403         )
 404
 405         counter, and_prestatements, result_expression = normalize_boolean_expression(
 406             counter,
 407             and_expression,
 408         )
 409
 410         result_prestatements = result_prestatements + and_prestatements
 411
 412     return (counter, result_prestatements, result_expression)
 413
 414 def normalize_boolean_expression(counter, expression):
 415     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 416     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 417
 418     result_variable = '${}'.format(counter)
 419     if_else_prestatment = NormalVariableInitializationStatement(
 420         variable=result_variable,
 421         expression=left_expression,
 422     )
 423     counter += 1
 424
 425     condition_expression=NormalVariableExpression(variable=result_variable)
 426     short_circuited_statements = right_prestatements + (NormalVariableReassignmentStatement(variable=result_variable, expression=right_expression),)
 427
 428     if expression.operator == 'and':
 429         if_else_statement = NormalIfElseStatement(
 430             condition_expression=condition_expression,
 431             if_statement_list=short_circuited_statements,
 432             else_statement_list=(),
 433         )
 434
 435     elif expression.operator == 'or':
 436         if_else_statement = NormalIfElseStatement(
 437             condition_expression=condition_expression,
 438             if_statement_list=(),
 439             else_statement_list=short_circuited_statements,
 440         )
 441
 442     else:
 443         raise Exception('Unable to handle operator "{}"'.format(expression.operator))
 444
 445     return (
 446         counter,
 447         left_prestatements + (if_else_prestatment, if_else_statement),
 448         NormalVariableExpression(variable=result_variable),
 449     )
 450
 451
 452 def normalize_infix_expression(counter, expression):
 453     return {
 454         'multiplication_level': normalize_basic_infix_operation,
 455         'addition_level': normalize_basic_infix_operation,
 456         'comparison_level': normalize_comparison_expression,
 457         'and_level': normalize_boolean_expression,
 458         'or_level': normalize_boolean_expression,
 459     }[expression.order](counter, expression)
 460
 461 def normalize_if_expression(counter, expression):
 462     counter, condition_prestatements, condition_expression = normalize_expression(
 463         counter,
 464         expression.condition_expression,
 465     )
 466
 467     result_variable = '${}'.format(counter)
 468     counter += 1
 469
 470     counter, if_statement_list = normalize_statement_list(
 471         counter,
 472         expression.if_statement_list,
 473         assign_result_to=result_variable,
 474     )
 475     counter, else_statement_list = normalize_statement_list(
 476         counter,
 477         expression.else_statement_list,
 478         assign_result_to=result_variable,
 479     )
 480
 481     return (
 482         counter,
 483         condition_prestatements + (
 484             NormalVariableInitializationStatement(
 485                 variable=result_variable,
 486                 expression=NormalVariableExpression(variable='builtin$nil'),
 487             ),
 488             NormalIfElseStatement(
 489                 condition_expression=condition_expression,
 490                 if_statement_list=if_statement_list,
 491                 else_statement_list=else_statement_list,
 492             ),
 493         ),
 494         NormalVariableExpression(variable=result_variable),
 495     )
 496
 497 def normalize_negation_expression(counter, expression):
 498     counter, prestatements, internal_expression = normalize_expression(counter, expression.value)
 499
 500     internal_variable = '${}'.format(counter)
 501     counter += 1
 502
 503     return (
 504         counter,
 505         prestatements + (
 506             NormalVariableInitializationStatement(
 507                 variable=internal_variable,
 508                 expression=internal_expression,
 509             ),
 510         ),
 511         NormalNegationExpression(internal_expression=NormalVariableExpression(variable=internal_variable)),
 512     )
 513
 514 def normalize_expression(counter, expression):
 515     return {
 516         NormalInfixExpression: fake_normalization,
 517         NormalVariableExpression: fake_normalization,
 518         parsing.FurFunctionCallExpression: normalize_function_call_expression,
 519         parsing.FurIfExpression: normalize_if_expression,
 520         parsing.FurInfixExpression: normalize_infix_expression,
 521         parsing.FurIntegerLiteralExpression: normalize_integer_literal_expression,
 522         parsing.FurListLiteralExpression: normalize_list_literal_expression,
 523         parsing.FurListItemExpression: normalize_list_item_expression,
 524         parsing.FurNegationExpression: normalize_negation_expression,
 525         parsing.FurStringLiteralExpression: normalize_string_literal_expression,
 526         parsing.FurSymbolExpression: normalize_symbol_expression,
 527     }[type(expression)](counter, expression)
 528
 529 def normalize_expression_statement(counter, statement):
 530     # TODO Normalized will be a NormalVariableExpression, which will go unused
 531     # for expression statements in every case except when it's a return
 532     # statement. This cases warnings on C compilation. We should only generate
 533     # this variable when it will be used on return.
 534     counter, prestatements, normalized = normalize_expression(counter, statement.expression)
 535
 536     return (
 537         counter,
 538         prestatements,
 539         NormalExpressionStatement(expression=normalized),
 540     )
 541
 542 def normalize_function_definition_statement(counter, statement):
 543     _, statement_list = normalize_statement_list(
 544         0,
 545         statement.statement_list,
 546         assign_result_to='result',
 547     )
 548     return (
 549         counter,
 550         (),
 551         NormalFunctionDefinitionStatement(
 552             name=statement.name,
 553             argument_name_list=statement.argument_name_list,
 554             statement_list=statement_list,
 555         ),
 556     )
 557
 558 def normalize_assignment_statement(counter, statement):
 559     counter, prestatements, normalized_expression = normalize_expression(counter, statement.expression)
 560     return (
 561         counter,
 562         prestatements,
 563         NormalAssignmentStatement(
 564             target=statement.target,
 565             expression=normalized_expression,
 566         ),
 567     )
 568
 569 def normalize_statement(counter, statement):
 570     return {
 571         parsing.FurAssignmentStatement: normalize_assignment_statement,
 572         parsing.FurExpressionStatement: normalize_expression_statement,
 573         parsing.FurFunctionDefinitionStatement: normalize_function_definition_statement,
 574     }[type(statement)](counter, statement)
 575
 576 @util.force_generator(tuple)
 577 def normalize_statement_list(counter, statement_list, **kwargs):
 578     assign_result_to = kwargs.pop('assign_result_to', None)
 579
 580     assert len(kwargs) == 0
 581
 582     result_statement_list = []
 583
 584     for statement in statement_list:
 585         counter, prestatements, normalized = normalize_statement(counter, statement)
 586         for s in prestatements:
 587             result_statement_list.append(s)
 588         result_statement_list.append(normalized)
 589
 590     last_statement = result_statement_list[-1]
 591
 592     if isinstance(last_statement, NormalExpressionStatement) and isinstance(last_statement.expression, NormalVariableExpression):
 593         result_expression = result_statement_list.pop().expression
 594
 595         if assign_result_to is not None:
 596             result_statement_list.append(
 597                 NormalVariableReassignmentStatement(
 598                     variable=assign_result_to,
 599                     expression=result_expression,
 600                 )
 601             )
 602
 603     return (
 604         counter,
 605         result_statement_list,
 606     )
 607
 608 def normalize(program):
 609     _, statement_list = normalize_statement_list(0, program.statement_list)
 610
 611     return NormalProgram(
 612         statement_list=statement_list,
 613     )