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     return (
 297         counter,
 298         tuple(prestatements),
 299         NormalFunctionCallExpression(
 300             function_expression=function_expression,
 301             argument_count=len(arguments),
 302             argument_items=NormalVariableExpression(variable=arguments_variable),
 303         ),
 304     )
 305
 306 def normalize_basic_infix_operation(counter, expression):
 307     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 308     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 309
 310     left_variable = '${}'.format(counter)
 311     counter += 1
 312     right_variable = '${}'.format(counter)
 313     counter += 1
 314     center_variable = '${}'.format(counter)
 315     counter += 1
 316
 317     root_prestatements = (
 318         NormalVariableInitializationStatement(
 319             variable=left_variable,
 320             expression=left_expression,
 321         ),
 322         NormalVariableInitializationStatement(
 323             variable=right_variable,
 324             expression=right_expression,
 325         ),
 326         NormalVariableInitializationStatement(
 327             variable=center_variable,
 328             expression=NormalInfixExpression(
 329                 order=expression.order,
 330                 operator=expression.operator,
 331                 left=NormalVariableExpression(variable=left_variable),
 332                 right=NormalVariableExpression(variable=right_variable),
 333             ),
 334         ),
 335     )
 336
 337     return (
 338         counter,
 339         left_prestatements + right_prestatements + root_prestatements,
 340         NormalVariableExpression(variable=center_variable),
 341     )
 342
 343 def normalize_comparison_expression(counter, expression):
 344     stack = []
 345
 346     while isinstance(expression.left, parsing.FurInfixExpression) and expression.order == 'comparison_level':
 347         stack.append((expression.operator, expression.order, expression.right))
 348         expression = expression.left
 349
 350     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 351     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 352
 353     left_variable = '${}'.format(counter)
 354     counter += 1
 355     right_variable = '${}'.format(counter)
 356     counter += 1
 357
 358     root_prestatements = (
 359         NormalVariableInitializationStatement(
 360             variable=left_variable,
 361             expression=left_expression,
 362         ),
 363         NormalVariableInitializationStatement(
 364             variable=right_variable,
 365             expression=right_expression,
 366         ),
 367     )
 368
 369     counter, result_prestatements, result_expression = (
 370         counter,
 371         left_prestatements + right_prestatements + root_prestatements,
 372         NormalInfixExpression(
 373             order=expression.order,
 374             operator=expression.operator,
 375             left=NormalVariableExpression(variable=left_variable),
 376             right=NormalVariableExpression(variable=right_variable),
 377         ),
 378     )
 379
 380     while len(stack) > 0:
 381         right_operator, right_order, right_expression = stack.pop()
 382         and_right_expression = parsing.FurInfixExpression(
 383             operator=right_operator,
 384             order=right_order,
 385             left=NormalVariableExpression(variable=right_variable),
 386             right=right_expression,
 387         )
 388
 389         and_expression = parsing.FurInfixExpression(
 390             operator='and',
 391             order='and_level',
 392             left=result_expression,
 393             right=and_right_expression,
 394         )
 395
 396         counter, and_prestatements, result_expression = normalize_boolean_expression(
 397             counter,
 398             and_expression,
 399         )
 400
 401         result_prestatements = result_prestatements + and_prestatements
 402
 403     return (counter, result_prestatements, result_expression)
 404
 405 def normalize_boolean_expression(counter, expression):
 406     counter, left_prestatements, left_expression = normalize_expression(counter, expression.left)
 407     counter, right_prestatements, right_expression = normalize_expression(counter, expression.right)
 408
 409     result_variable = '${}'.format(counter)
 410     if_else_prestatment = NormalVariableInitializationStatement(
 411         variable=result_variable,
 412         expression=left_expression,
 413     )
 414     counter += 1
 415
 416     condition_expression=NormalVariableExpression(variable=result_variable)
 417     short_circuited_statements = right_prestatements + (NormalVariableReassignmentStatement(variable=result_variable, expression=right_expression),)
 418
 419     if expression.operator == 'and':
 420         if_else_statement = NormalIfElseStatement(
 421             condition_expression=condition_expression,
 422             if_statement_list=short_circuited_statements,
 423             else_statement_list=(),
 424         )
 425
 426     elif expression.operator == 'or':
 427         if_else_statement = NormalIfElseStatement(
 428             condition_expression=condition_expression,
 429             if_statement_list=(),
 430             else_statement_list=short_circuited_statements,
 431         )
 432
 433     else:
 434         raise Exception('Unable to handle operator "{}"'.format(expression.operator))
 435
 436     return (
 437         counter,
 438         left_prestatements + (if_else_prestatment, if_else_statement),
 439         NormalVariableExpression(variable=result_variable),
 440     )
 441
 442
 443 def normalize_infix_expression(counter, expression):
 444     return {
 445         'multiplication_level': normalize_basic_infix_operation,
 446         'addition_level': normalize_basic_infix_operation,
 447         'comparison_level': normalize_comparison_expression,
 448         'and_level': normalize_boolean_expression,
 449         'or_level': normalize_boolean_expression,
 450     }[expression.order](counter, expression)
 451
 452 def normalize_if_expression(counter, expression):
 453     counter, condition_prestatements, condition_expression = normalize_expression(
 454         counter,
 455         expression.condition_expression,
 456     )
 457
 458     result_variable = '${}'.format(counter)
 459     counter += 1
 460
 461     counter, if_statement_list = normalize_statement_list(
 462         counter,
 463         expression.if_statement_list,
 464         assign_result_to=result_variable,
 465     )
 466     counter, else_statement_list = normalize_statement_list(
 467         counter,
 468         expression.else_statement_list,
 469         assign_result_to=result_variable,
 470     )
 471
 472     return (
 473         counter,
 474         condition_prestatements + (
 475             NormalVariableInitializationStatement(
 476                 variable=result_variable,
 477                 expression=NormalVariableExpression(variable='builtin$nil'),
 478             ),
 479             NormalIfElseStatement(
 480                 condition_expression=condition_expression,
 481                 if_statement_list=if_statement_list,
 482                 else_statement_list=else_statement_list,
 483             ),
 484         ),
 485         NormalVariableExpression(variable=result_variable),
 486     )
 487
 488 def normalize_negation_expression(counter, expression):
 489     counter, prestatements, internal_expression = normalize_expression(counter, expression.value)
 490
 491     internal_variable = '${}'.format(counter)
 492     counter += 1
 493
 494     return (
 495         counter,
 496         prestatements + (
 497             NormalVariableInitializationStatement(
 498                 variable=internal_variable,
 499                 expression=internal_expression,
 500             ),
 501         ),
 502         NormalNegationExpression(internal_expression=NormalVariableExpression(variable=internal_variable)),
 503     )
 504
 505 def normalize_expression(counter, expression):
 506     return {
 507         NormalInfixExpression: fake_normalization,
 508         NormalVariableExpression: fake_normalization,
 509         parsing.FurFunctionCallExpression: normalize_function_call_expression,
 510         parsing.FurIfExpression: normalize_if_expression,
 511         parsing.FurInfixExpression: normalize_infix_expression,
 512         parsing.FurIntegerLiteralExpression: normalize_integer_literal_expression,
 513         parsing.FurListLiteralExpression: normalize_list_literal_expression,
 514         parsing.FurListItemExpression: normalize_list_item_expression,
 515         parsing.FurNegationExpression: normalize_negation_expression,
 516         parsing.FurStringLiteralExpression: normalize_string_literal_expression,
 517         parsing.FurSymbolExpression: normalize_symbol_expression,
 518     }[type(expression)](counter, expression)
 519
 520 def normalize_expression_statement(counter, statement):
 521     # TODO Normalized will be a NormalVariableExpression, which will go unused
 522     # for expression statements in every case except when it's a return
 523     # statement. This cases warnings on C compilation. We should only generate
 524     # this variable when it will be used on return.
 525     counter, prestatements, normalized = normalize_expression(counter, statement.expression)
 526
 527     return (
 528         counter,
 529         prestatements,
 530         NormalExpressionStatement(expression=normalized),
 531     )
 532
 533 def normalize_function_definition_statement(counter, statement):
 534     _, statement_list = normalize_statement_list(
 535         0,
 536         statement.statement_list,
 537         assign_result_to='result',
 538     )
 539     return (
 540         counter,
 541         (),
 542         NormalFunctionDefinitionStatement(
 543             name=statement.name,
 544             argument_name_list=statement.argument_name_list,
 545             statement_list=statement_list,
 546         ),
 547     )
 548
 549 def normalize_assignment_statement(counter, statement):
 550     counter, prestatements, normalized_expression = normalize_expression(counter, statement.expression)
 551     return (
 552         counter,
 553         prestatements,
 554         NormalAssignmentStatement(
 555             target=statement.target,
 556             expression=normalized_expression,
 557         ),
 558     )
 559
 560 def normalize_statement(counter, statement):
 561     return {
 562         parsing.FurAssignmentStatement: normalize_assignment_statement,
 563         parsing.FurExpressionStatement: normalize_expression_statement,
 564         parsing.FurFunctionDefinitionStatement: normalize_function_definition_statement,
 565     }[type(statement)](counter, statement)
 566
 567 @util.force_generator(tuple)
 568 def normalize_statement_list(counter, statement_list, **kwargs):
 569     assign_result_to = kwargs.pop('assign_result_to', None)
 570
 571     assert len(kwargs) == 0
 572
 573     result_statement_list = []
 574
 575     for statement in statement_list:
 576         counter, prestatements, normalized = normalize_statement(counter, statement)
 577         for s in prestatements:
 578             result_statement_list.append(s)
 579         result_statement_list.append(normalized)
 580
 581     last_statement = result_statement_list[-1]
 582
 583     if isinstance(last_statement, NormalExpressionStatement) and isinstance(last_statement.expression, NormalVariableExpression):
 584         result_expression = result_statement_list.pop().expression
 585
 586         if assign_result_to is not None:
 587             result_statement_list.append(
 588                 NormalVariableReassignmentStatement(
 589                     variable=assign_result_to,
 590                     expression=result_expression,
 591                 )
 592             )
 593
 594     return (
 595         counter,
 596         result_statement_list,
 597     )
 598
 599 def normalize(program):
 600     _, statement_list = normalize_statement_list(0, program.statement_list)
 601
 602     return NormalProgram(
 603         statement_list=statement_list,
 604     )