X-Git-Url: https://code.kerkeslager.com/?a=blobdiff_plain;f=normalization.py;h=762a8f1aa39e333e473c3fadbbc925f45377cb33;hb=02d64def49065ad614fe0ee2a85060666552192e;hp=1da656958bd91b78ea41a7017257f1584af4f03e;hpb=1852539af30c364a11d2e2a0bb7944102293dcf6;p=fur diff --git a/normalization.py b/normalization.py index 1da6569..762a8f1 100644 --- a/normalization.py +++ b/normalization.py @@ -1,6 +1,7 @@ import collections import parsing +import util NormalVariableExpression = collections.namedtuple( 'NormalVariableExpression', @@ -9,6 +10,27 @@ NormalVariableExpression = collections.namedtuple( ], ) +NormalIntegerLiteralExpression = collections.namedtuple( + 'NormalIntegerLiteralExpression', + [ + 'integer', + ], +) + +NormalStringLiteralExpression = collections.namedtuple( + 'NormalStringLiteralExpression', + [ + 'string', + ], +) + +NormalSymbolExpression = collections.namedtuple( + 'NormalSymbolExpression', + [ + 'symbol', + ], +) + NormalNegationExpression = collections.namedtuple( 'NormalNegationExpression', [ @@ -29,8 +51,17 @@ NormalInfixExpression = collections.namedtuple( NormalFunctionCallExpression = collections.namedtuple( 'NormalFunctionCallExpression', [ - 'function', - 'arguments', + 'function_expression', + 'argument_count', + 'argument_items', + ], +) + +NormalArrayVariableInitializationStatement = collections.namedtuple( + 'NormalArrayVariableInitializationStatement', + [ + 'variable', + 'items', ], ) @@ -57,12 +88,29 @@ NormalExpressionStatement = collections.namedtuple( ], ) +NormalAssignmentStatement = collections.namedtuple( + 'NormalAssignmentStatement', + [ + 'target', + 'expression', + ], +) + NormalIfElseStatement = collections.namedtuple( 'NormalIfElseStatement', [ 'condition_expression', - 'if_statements', - 'else_statements', + 'if_statement_list', + 'else_statement_list', + ], +) + +NormalFunctionDefinitionStatement = collections.namedtuple( + 'NormalFunctionDefinitionStatement', + [ + 'name', + 'argument_name_list', + 'statement_list', ], ) @@ -76,6 +124,122 @@ NormalProgram = collections.namedtuple( def fake_normalization(counter, thing): return (counter, (), thing) +def normalize_integer_literal_expression(counter, expression): + variable = '${}'.format(counter) + return ( + counter + 1, + ( + NormalVariableInitializationStatement( + variable=variable, + expression=NormalIntegerLiteralExpression(integer=expression.integer), + ), + ), + NormalVariableExpression(variable=variable), + ) + +NormalListConstructExpression = collections.namedtuple( + 'NormalListConstructExpression', + [ + 'allocate', + ], +) + +NormalListAppendStatement = collections.namedtuple( + 'NormalListAppendStatement', + [ + 'list_expression', + 'item_expression', + ], +) + +NormalListGetExpression = collections.namedtuple( + 'NormalListGetExpression', + [ + 'list_expression', + 'index_expression', + ], +) + +def normalize_list_literal_expression(counter, expression): + list_variable = '${}'.format(counter) + counter += 1 + + prestatements = [ + NormalVariableInitializationStatement( + variable=list_variable, + expression=NormalListConstructExpression(allocate=len(expression.item_expression_list)), + ), + ] + + list_expression = NormalVariableExpression(variable=list_variable) + + for item_expression in expression.item_expression_list: + counter, item_expression_prestatements, normalized = normalize_expression( + counter, + item_expression, + ) + + for p in item_expression_prestatements: + prestatements.append(p) + + prestatements.append( + NormalListAppendStatement( + list_expression=list_expression, + item_expression=normalized, + ) + ) + + return ( + counter, + tuple(prestatements), + list_expression, + ) + +def normalize_list_item_expression(counter, expression): + counter, list_prestatements, list_expression = normalize_expression(counter, expression.list_expression) + counter, index_prestatements, index_expression = normalize_expression(counter, expression.index_expression) + + result_variable = '${}'.format(counter) + result_prestatement = NormalVariableInitializationStatement( + variable=result_variable, + expression=NormalListGetExpression( + list_expression=list_expression, + index_expression=index_expression, + ), + ) + + return ( + counter + 1, + list_prestatements + index_prestatements + (result_prestatement,), + NormalVariableExpression(variable=result_variable), + ) + +def normalize_string_literal_expression(counter, expression): + variable = '${}'.format(counter) + return ( + counter + 1, + ( + NormalVariableInitializationStatement( + variable=variable, + expression=NormalStringLiteralExpression(string=expression.string), + ), + ), + NormalVariableExpression(variable=variable), + ) + +def normalize_symbol_expression(counter, expression): + variable = '${}'.format(counter) + return ( + counter + 1, + ( + NormalVariableInitializationStatement( + variable=variable, + expression=NormalSymbolExpression(symbol=expression.symbol), + ), + ), + NormalVariableExpression(variable=variable), + ) + def normalize_function_call_expression(counter, expression): assert isinstance(expression, parsing.FurFunctionCallExpression) @@ -89,22 +253,63 @@ def normalize_function_call_expression(counter, expression): prestatements.append(s) variable = '${}'.format(counter) - prestatements.append(NormalVariableInitializationStatement( - variable=variable, - expression=normalized_argument, - )) + prestatements.append( + NormalVariableInitializationStatement( + variable=variable, + expression=normalized_argument, + ) + ) arguments.append(NormalVariableExpression( variable=variable, )) counter += 1 - return ( + arguments_variable = '${}'.format(counter) + counter += 1 + + prestatements.append(NormalArrayVariableInitializationStatement( + variable=arguments_variable, + items=tuple(arguments), + )) + + counter, function_prestatements, function_expression = normalize_expression( counter, + expression.function, + ) + + for ps in function_prestatements: + prestatements.append(ps) + + if not isinstance(function_expression, NormalVariableExpression): + function_variable = '${}'.format(counter) + + prestatements.append( + NormalVariableInitializationStatement( + variable=function_variable, + expression=function_expression, + ) + ) + + function_expression = NormalVariableExpression(variable=function_variable) + counter += 1 + + result_variable = '${}'.format(counter) + + prestatements.append( + NormalVariableInitializationStatement( + variable=result_variable, + expression=NormalFunctionCallExpression( + function_expression=function_expression, + argument_count=len(arguments), + argument_items=NormalVariableExpression(variable=arguments_variable), + ), + ) + ) + + return ( + counter + 1, tuple(prestatements), - NormalFunctionCallExpression( - expression.function, # TODO Normalize the function - arguments=tuple(arguments), - ), + NormalVariableExpression(variable=result_variable), ) def normalize_basic_infix_operation(counter, expression): @@ -115,6 +320,8 @@ def normalize_basic_infix_operation(counter, expression): counter += 1 right_variable = '${}'.format(counter) counter += 1 + center_variable = '${}'.format(counter) + counter += 1 root_prestatements = ( NormalVariableInitializationStatement( @@ -125,17 +332,21 @@ def normalize_basic_infix_operation(counter, expression): variable=right_variable, expression=right_expression, ), + NormalVariableInitializationStatement( + variable=center_variable, + expression=NormalInfixExpression( + order=expression.order, + operator=expression.operator, + left=NormalVariableExpression(variable=left_variable), + right=NormalVariableExpression(variable=right_variable), + ), + ), ) return ( counter, left_prestatements + right_prestatements + root_prestatements, - NormalInfixExpression( - order=expression.order, # TODO Do we need this? - operator=expression.operator, - left=NormalVariableExpression(variable=left_variable), - right=NormalVariableExpression(variable=right_variable), - ), + NormalVariableExpression(variable=center_variable), ) def normalize_comparison_expression(counter, expression): @@ -167,9 +378,8 @@ def normalize_comparison_expression(counter, expression): counter, result_prestatements, result_expression = ( counter, left_prestatements + right_prestatements + root_prestatements, - # TODO Implement short-circuiting NormalInfixExpression( - order=expression.order, # TODO Do we need this? + order=expression.order, operator=expression.operator, left=NormalVariableExpression(variable=left_variable), right=NormalVariableExpression(variable=right_variable), @@ -206,7 +416,10 @@ def normalize_boolean_expression(counter, expression): counter, right_prestatements, right_expression = normalize_expression(counter, expression.right) result_variable = '${}'.format(counter) - if_else_prestatment = NormalVariableInitializationStatement(variable=result_variable, expression=left_expression) + if_else_prestatment = NormalVariableInitializationStatement( + variable=result_variable, + expression=left_expression, + ) counter += 1 condition_expression=NormalVariableExpression(variable=result_variable) @@ -215,15 +428,15 @@ def normalize_boolean_expression(counter, expression): if expression.operator == 'and': if_else_statement = NormalIfElseStatement( condition_expression=condition_expression, - if_statements=short_circuited_statements, - else_statements=(), + if_statement_list=short_circuited_statements, + else_statement_list=(), ) elif expression.operator == 'or': if_else_statement = NormalIfElseStatement( condition_expression=condition_expression, - if_statements=(), - else_statements=short_circuited_statements, + if_statement_list=(), + else_statement_list=short_circuited_statements, ) else: @@ -245,6 +458,42 @@ def normalize_infix_expression(counter, expression): 'or_level': normalize_boolean_expression, }[expression.order](counter, expression) +def normalize_if_expression(counter, expression): + counter, condition_prestatements, condition_expression = normalize_expression( + counter, + expression.condition_expression, + ) + + result_variable = '${}'.format(counter) + counter += 1 + + counter, if_statement_list = normalize_statement_list( + counter, + expression.if_statement_list, + assign_result_to=result_variable, + ) + counter, else_statement_list = normalize_statement_list( + counter, + expression.else_statement_list, + assign_result_to=result_variable, + ) + + return ( + counter, + condition_prestatements + ( + NormalVariableInitializationStatement( + variable=result_variable, + expression=NormalVariableExpression(variable='builtin$nil'), + ), + NormalIfElseStatement( + condition_expression=condition_expression, + if_statement_list=if_statement_list, + else_statement_list=else_statement_list, + ), + ), + NormalVariableExpression(variable=result_variable), + ) + def normalize_negation_expression(counter, expression): counter, prestatements, internal_expression = normalize_expression(counter, expression.value) @@ -253,30 +502,36 @@ def normalize_negation_expression(counter, expression): return ( counter, - prestatements + (NormalVariableInitializationStatement(variable=internal_variable, expression=internal_expression),), + prestatements + ( + NormalVariableInitializationStatement( + variable=internal_variable, + expression=internal_expression, + ), + ), NormalNegationExpression(internal_expression=NormalVariableExpression(variable=internal_variable)), ) -def normalize_parenthesized_expression(counter, expression): - return normalize_expression(counter, expression.internal) - def normalize_expression(counter, expression): return { NormalInfixExpression: fake_normalization, NormalVariableExpression: fake_normalization, parsing.FurFunctionCallExpression: normalize_function_call_expression, + parsing.FurIfExpression: normalize_if_expression, parsing.FurInfixExpression: normalize_infix_expression, - parsing.FurIntegerLiteralExpression: fake_normalization, + parsing.FurIntegerLiteralExpression: normalize_integer_literal_expression, + parsing.FurListLiteralExpression: normalize_list_literal_expression, + parsing.FurListItemExpression: normalize_list_item_expression, parsing.FurNegationExpression: normalize_negation_expression, - parsing.FurParenthesizedExpression: normalize_parenthesized_expression, - parsing.FurStringLiteralExpression: fake_normalization, - parsing.FurSymbolExpression: fake_normalization, + parsing.FurStringLiteralExpression: normalize_string_literal_expression, + parsing.FurSymbolExpression: normalize_symbol_expression, }[type(expression)](counter, expression) def normalize_expression_statement(counter, statement): - counter, prestatements, normalized = { - parsing.FurFunctionCallExpression: normalize_function_call_expression, - }[type(statement.expression)](counter, statement.expression) + # TODO Normalized will be a NormalVariableExpression, which will go unused + # for expression statements in every case except when it's a return + # statement. This cases warnings on C compilation. We should only generate + # this variable when it will be used on return. + counter, prestatements, normalized = normalize_expression(counter, statement.expression) return ( counter, @@ -284,21 +539,74 @@ def normalize_expression_statement(counter, statement): NormalExpressionStatement(expression=normalized), ) +def normalize_function_definition_statement(counter, statement): + _, statement_list = normalize_statement_list( + 0, + statement.statement_list, + assign_result_to='result', + ) + return ( + counter, + (), + NormalFunctionDefinitionStatement( + name=statement.name, + argument_name_list=statement.argument_name_list, + statement_list=statement_list, + ), + ) + +def normalize_assignment_statement(counter, statement): + counter, prestatements, normalized_expression = normalize_expression(counter, statement.expression) + return ( + counter, + prestatements, + NormalAssignmentStatement( + target=statement.target, + expression=normalized_expression, + ), + ) + def normalize_statement(counter, statement): return { + parsing.FurAssignmentStatement: normalize_assignment_statement, parsing.FurExpressionStatement: normalize_expression_statement, - parsing.FurAssignmentStatement: fake_normalization, + parsing.FurFunctionDefinitionStatement: normalize_function_definition_statement, }[type(statement)](counter, statement) -def normalize(program): - counter = 0 - statement_list = [] +@util.force_generator(tuple) +def normalize_statement_list(counter, statement_list, **kwargs): + assign_result_to = kwargs.pop('assign_result_to', None) + + assert len(kwargs) == 0 + + result_statement_list = [] - for statement in program.statement_list: + for statement in statement_list: counter, prestatements, normalized = normalize_statement(counter, statement) for s in prestatements: - statement_list.append(s) - statement_list.append(normalized) + result_statement_list.append(s) + result_statement_list.append(normalized) + + # TODO The way we fix the last statement is really confusing + last_statement = result_statement_list[-1] + + if isinstance(last_statement, NormalExpressionStatement) and isinstance(last_statement.expression, NormalVariableExpression): + if assign_result_to is not None: + result_expression = result_statement_list.pop().expression + result_statement_list.append( + NormalVariableReassignmentStatement( + variable=assign_result_to, + expression=result_expression, + ) + ) + + return ( + counter, + result_statement_list, + ) + +def normalize(program): + _, statement_list = normalize_statement_list(0, program.statement_list) return NormalProgram( statement_list=statement_list,