From b7a244b6319f5c770582283097f6184e5a6ec192 Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Tue, 1 Oct 2019 00:32:51 -0400 Subject: [PATCH] Variables and basic math --- c_generation.py | 6 +++ conversion.py | 11 ++++++ crossplatform_ir_generation.py | 26 ++++++++++++ desugaring.py | 14 +++++-- normalization.py | 36 ++++++++++------- templates/arithmetic_instruction.c | 14 +++++++ templates/environment.c | 63 ++++++++++++++++++++++++++++++ templates/program2.c | 51 +++++++++++++++++++++--- templates/stack.c | 14 +++---- 9 files changed, 205 insertions(+), 30 deletions(-) create mode 100644 templates/arithmetic_instruction.c create mode 100644 templates/environment.c diff --git a/c_generation.py b/c_generation.py index 6dd4551..2f4a9de 100644 --- a/c_generation.py +++ b/c_generation.py @@ -40,12 +40,18 @@ def generate_symbol_argument(argument): def generate_argument(instruction): try: return { + 'add': generate_size_t_argument, 'drop': generate_null_argument, 'end': generate_null_argument, 'call': generate_size_t_argument, + 'idiv': generate_size_t_argument, + 'mod': generate_size_t_argument, + 'mul': generate_size_t_argument, + 'pop': generate_symbol_argument, 'push': generate_symbol_argument, 'push_integer': generate_integer_argument, 'push_string': generate_string_argument, + 'sub': generate_size_t_argument, }[instruction.instruction](instruction.argument) except KeyError: diff --git a/conversion.py b/conversion.py index 04cbdab..29a40d7 100644 --- a/conversion.py +++ b/conversion.py @@ -2,6 +2,13 @@ import collections import normalization +CPSBuiltinExpression = collections.namedtuple( + 'CPSBuiltinExpression', + ( + 'symbol', + ), +) + CPSFunctionCallExpression = collections.namedtuple( 'CPSFunctionCallExpression', ( @@ -131,6 +138,9 @@ CPSProgram = collections.namedtuple( ), ) +def convert_builtin_expression(expression): + return CPSBuiltinExpression(symbol=expression.symbol) + def convert_function_call_expression(expression): return CPSFunctionCallExpression( metadata=expression.metadata, @@ -170,6 +180,7 @@ def convert_variable_expression(expression): def convert_expression(expression): return { + normalization.NormalBuiltinExpression: convert_builtin_expression, normalization.NormalFunctionCallExpression: convert_function_call_expression, normalization.NormalIfElseExpression: convert_if_else_expression, normalization.NormalIntegerLiteralExpression: convert_integer_literal_expression, diff --git a/crossplatform_ir_generation.py b/crossplatform_ir_generation.py index 09079cd..089b076 100644 --- a/crossplatform_ir_generation.py +++ b/crossplatform_ir_generation.py @@ -36,7 +36,33 @@ def generate_string_literal(string): def generate_symbol_literal(symbol): return 'sym({})'.format(symbol) +def generate_instruction_name_from_builtin(builtin): + try: + return { + '__add__': 'add', + '__subtract__': 'sub', + '__multiply__': 'mul', + '__integer_divide__': 'idiv', + '__modular_divide__': 'mod', + }[builtin] + + except KeyError: + import ipdb; ipdb.set_trace() + def generate_function_call_expression(counters, expression): + if isinstance(expression.function_expression, conversion.CPSBuiltinExpression): + return ( + (), + ( + CIRInstruction( + instruction=generate_instruction_name_from_builtin( + expression.function_expression.symbol, + ), + argument=expression.argument_count, + ), + ) + ) + referenced_entry_list, instruction_list = generate_expression( counters, expression.function_expression, diff --git a/desugaring.py b/desugaring.py index 47dfe6f..28d1a78 100644 --- a/desugaring.py +++ b/desugaring.py @@ -2,6 +2,14 @@ import collections import parsing +DesugaredBuiltinExpression = collections.namedtuple( + 'DesugaredBuiltinExpression', + ( + 'metadata', + 'symbol', + ), +) + DesugaredFunctionCallExpression = collections.namedtuple( 'DesugaredFunctionCallExpression', ( @@ -179,7 +187,7 @@ def desugar_infix_expression(expression): return DesugaredFunctionCallExpression( metadata=expression.metadata, - function=DesugaredSymbolExpression( + function=DesugaredBuiltinExpression( metadata=expression.metadata, symbol=function, ), @@ -203,7 +211,7 @@ def desugar_lambda_expression(expression): def desugar_list_item_expression(expression): return DesugaredFunctionCallExpression( metadata=expression.metadata, - function=DesugaredSymbolExpression( + function=DesugaredBuiltinExpression( metadata=expression.metadata, symbol='__get__', ), @@ -221,7 +229,7 @@ def desugar_list_literal_expression(expression): def desugar_negation_expression(expression): return DesugaredFunctionCallExpression( metadata=expression.metadata, - function=DesugaredSymbolExpression( + function=DesugaredBuiltinExpression( metadata=expression.metadata, symbol='__negate__', ), diff --git a/normalization.py b/normalization.py index 79fe5e0..83e24dd 100644 --- a/normalization.py +++ b/normalization.py @@ -3,6 +3,13 @@ import collections import desugaring import util +NormalBuiltinExpression = collections.namedtuple( + 'NormalBuiltinExpression', + ( + 'symbol', + ), +) + NormalVariableExpression = collections.namedtuple( 'NormalVariableExpression', [ @@ -102,6 +109,13 @@ NormalProgram = collections.namedtuple( ], ) +def normalize_builtin_expression(counter, expression): + return ( + counter, + (), + NormalBuiltinExpression(symbol=expression.symbol), + ) + def normalize_integer_literal_expression(counter, expression): return ( counter, @@ -240,23 +254,14 @@ def normalize_function_call_expression(counter, expression): for ps in function_prestatements: prestatements.append(ps) - result_variable = '${}'.format(counter) - - prestatements.append( - NormalVariableInitializationStatement( - variable=result_variable, - expression=NormalFunctionCallExpression( - metadata=expression.metadata, - function_expression=function_expression, - argument_count=len(expression.argument_list), - ), - ) - ) - return ( - counter + 1, + counter, tuple(prestatements), - NormalVariableExpression(variable=result_variable), + NormalFunctionCallExpression( + metadata=expression.metadata, + function_expression=function_expression, + argument_count=len(expression.argument_list), + ), ) def normalize_if_expression(counter, expression): @@ -286,6 +291,7 @@ def normalize_if_expression(counter, expression): def normalize_expression(counter, expression): return { + desugaring.DesugaredBuiltinExpression: normalize_builtin_expression, desugaring.DesugaredFunctionCallExpression: normalize_function_call_expression, desugaring.DesugaredIfExpression: normalize_if_expression, desugaring.DesugaredIntegerLiteralExpression: normalize_integer_literal_expression, diff --git a/templates/arithmetic_instruction.c b/templates/arithmetic_instruction.c new file mode 100644 index 0000000..a78a579 --- /dev/null +++ b/templates/arithmetic_instruction.c @@ -0,0 +1,14 @@ +void {{ name }}(struct Thread* thread, const union Argument argument) { + // We're going to reuse result as both the addend and the sum + assert(!Stack_isEmpty(&(thread->stack))); + Object result = Stack_pop(&(thread->stack)); + assert(result.type == INTEGER); + + assert(!Stack_isEmpty(&(thread->stack))); + Object other = Stack_pop(&(thread->stack)); + assert(result.type == INTEGER); + + result.value.integer = other.value.integer {{ operation }} result.value.integer; + + Stack_push(&(thread->stack), result); +} diff --git a/templates/environment.c b/templates/environment.c new file mode 100644 index 0000000..4ed5302 --- /dev/null +++ b/templates/environment.c @@ -0,0 +1,63 @@ +struct _EnvironmentNode; +typedef struct _EnvironmentNode _EnvironmentNode; +struct _EnvironmentNode { + const char* symbol; + Object value; + _EnvironmentNode* next; +}; + +struct Environment; +typedef struct Environment Environment; +struct Environment { + _EnvironmentNode* top; +}; + +struct Environment_get_Result; +typedef struct Environment_get_Result Environment_get_Result; +struct Environment_get_Result { + bool found; + Object result; +}; + +void Environment_initialize(Environment* self) { + self->top = NULL; +} + +void Environment_deinitialize(Environment* self) { + while(self->top != NULL) { + _EnvironmentNode* en = self->top; + self->top = en->next; + Object_deinitialize(&(en->value)); + free(en); + } +} + +Environment* Environment_construct() { + Environment* result = malloc(sizeof(Environment)); + Environment_initialize(result); + return result; +} + +void Environment_destruct(Environment* self) { + Environment_deinitialize(self); + free(self); +} + +Environment_get_Result Environment_get(Environment* self, char* symbol) { + for(_EnvironmentNode* current = self->top; current != NULL; current = current->next) { + if(strcmp(current->symbol, symbol) == 0) { + return (Environment_get_Result) { true, current->value }; + } + } + return (Environment_get_Result) { false, BUILTIN_NIL }; +} + +void Environment_set(Environment* self, char* symbol, Object value) { + assert(!(Environment_get(self, symbol).found)); + + _EnvironmentNode* en = malloc(sizeof(_EnvironmentNode)); + en->symbol = symbol; + en->value = value; + en->next = self->top; + self->top = en; +} diff --git a/templates/program2.c b/templates/program2.c index 6e21ce0..8abe2a2 100644 --- a/templates/program2.c +++ b/templates/program2.c @@ -40,21 +40,25 @@ struct Object { void Object_deinitialize(Object* self) { } +{% include "environment.c" %} {% include "stack.c" %} struct Thread; typedef struct Thread Thread; struct Thread { + Environment* environment; Stack stack; size_t program_counter; }; void Thread_initialize(Thread* self, size_t program_counter) { + self->environment = Environment_construct(); Stack_initialize(&(self->stack)); self->program_counter = program_counter; } void Thread_deinitialize(Thread* self) { + Environment_destruct(self->environment); Stack_deinitialize(&(self->stack)); } @@ -107,6 +111,11 @@ void call(struct Thread* thread, const union Argument argument) { } } +{% with name='add', operation='+' %} + {% include "arithmetic_instruction.c" %} +{% endwith %} + + void drop(struct Thread* thread, const union Argument argument) { assert(!Stack_isEmpty(&(thread->stack))); Object result = Stack_pop(&(thread->stack)); @@ -116,19 +125,47 @@ void drop(struct Thread* thread, const union Argument argument) { void end(struct Thread* thread, const union Argument argument) { } -void push(struct Thread* thread, const union Argument argument) { +{% with name='idiv', operation='/' %} + {% include "arithmetic_instruction.c" %} +{% endwith %} + +{% with name='mod', operation='%' %} + {% include "arithmetic_instruction.c" %} +{% endwith %} + +{% with name='mul', operation='*' %} + {% include "arithmetic_instruction.c" %} +{% endwith %} + +void pop(struct Thread* thread, const union Argument argument) { char* argumentString = argument.string; - Object result; + assert(!Stack_isEmpty(&(thread->stack))); + Object result = Stack_pop(&(thread->stack)); if(strcmp(argumentString, "print") == 0) { + assert(false); + } + + Environment_set(thread->environment, argumentString, result); +} + +void push(struct Thread* thread, const union Argument argument) { + char* argumentString = argument.string; + + if(strcmp(argumentString, "print") == 0) { + Object result; result.type = BUILTIN; result.value.builtin = PRINT; + Stack_push(&(thread->stack), result); } else { - assert(false); + Environment_get_Result result = Environment_get(thread->environment, argumentString); + if(!result.found) { + fprintf(stderr, "Variable `%s` not found", argumentString); + assert(false); + } + Stack_push(&(thread->stack), result.result); } - - Stack_push(&(thread->stack), result); } void push_integer(struct Thread* thread, const union Argument argument) { @@ -147,6 +184,10 @@ void push_string(struct Thread* thread, const union Argument argument) { Stack_push(&(thread->stack), result); } +{% with name='sub', operation='-' %} + {% include "arithmetic_instruction.c" %} +{% endwith %} + struct Instruction; typedef const struct Instruction Instruction; struct Instruction { diff --git a/templates/stack.c b/templates/stack.c index bf9c7a5..537321e 100644 --- a/templates/stack.c +++ b/templates/stack.c @@ -1,14 +1,14 @@ -struct StackNode; -typedef struct StackNode StackNode; -struct StackNode { +struct _StackNode; +typedef struct _StackNode _StackNode; +struct _StackNode { Object value; - StackNode* next; + _StackNode* next; }; struct Stack; typedef struct Stack Stack; struct Stack { - StackNode* top; + _StackNode* top; }; void Stack_initialize(Stack* self) { @@ -29,7 +29,7 @@ void Stack_deinitialize(Stack* self) { } void Stack_push(Stack* self, Object value) { - StackNode* node = malloc(sizeof(StackNode)); + _StackNode* node = malloc(sizeof(_StackNode)); node->value = value; node->next = self->top; self->top = node; @@ -38,7 +38,7 @@ void Stack_push(Stack* self, Object value) { Object Stack_pop(Stack* self) { assert(self->top != NULL); - StackNode* node = self->top; + _StackNode* node = self->top; self->top = node->next; Object result = node->value; -- 2.20.1