diff options
Diffstat (limited to 'interpreter')
| -rw-r--r-- | interpreter/Makefile | 4 | ||||
| -rw-r--r-- | interpreter/code.c | 57 | ||||
| -rw-r--r-- | interpreter/code.h | 10 | ||||
| -rw-r--r-- | interpreter/eval.c | 233 | ||||
| -rw-r--r-- | interpreter/graphs.c | 134 | ||||
| -rw-r--r-- | interpreter/graphs.h | 26 | ||||
| -rw-r--r-- | interpreter/print.c | 9 | ||||
| -rw-r--r-- | interpreter/print.h | 3 |
8 files changed, 322 insertions, 154 deletions
diff --git a/interpreter/Makefile b/interpreter/Makefile index 246dd03..56619ce 100644 --- a/interpreter/Makefile +++ b/interpreter/Makefile @@ -1,7 +1,7 @@ CFLAGS=-Wall -Werror -g -DEPS=lex.h syntax.h print.h parse.h log.h eval.h mem.h code.h -OBJ=fuspel.o lex.o syntax.o print.o parse.o log.o eval.o mem.o code.o +DEPS=lex.h syntax.h print.h parse.h log.h eval.h mem.h code.h graphs.h +OBJ=fuspel.o lex.o syntax.o print.o parse.o log.o eval.o mem.o code.o graphs.o EXE=fuspel .PHONY: all clean diff --git a/interpreter/code.c b/interpreter/code.c index a306e02..c194d02 100644 --- a/interpreter/code.c +++ b/interpreter/code.c @@ -1,59 +1,46 @@ #include "code.h" -#include <stdio.h> #include <string.h> #include <time.h> #include "mem.h" -#include "print.h" -expression* make_int_expression(int i) { - expression* result = my_calloc(1, sizeof(expression)); - result->kind = EXPR_INT; - result->var1 = my_calloc(1, sizeof(int)); - *((int*) result->var1) = i; - return result; +void fill_node_int(struct node** node, int i) { + free_node(*node, 0); + (*node)->kind = EXPR_INT; + (*node)->var1 = my_calloc(1, sizeof(int)); + *((int*) (*node)->var1) = i; } -expression* make_name_expression(char* s) { - expression* result = my_calloc(1, sizeof(expression)); - result->kind = EXPR_NAME; - result->var1 = my_calloc(1, strlen(s) + 1); - strcpy(result->var1, s); - return result; +void fill_node_name(struct node** node, char* s) { + free_node(*node, 0); + (*node)->kind = EXPR_NAME; + (*node)->var1 = my_calloc(1, strlen(s) + 1); + strcpy((*node)->var1, s); } -expression* code_time(void) { - return make_int_expression((int) time(NULL)); +void code_time(struct node** result) { + fill_node_int(result, (int) time(NULL)); } -expression* code_print(expression* expr) { - expression* result = my_calloc(1, sizeof(expression)); - cpy_expression(result, expr); - print_expression(expr); - printf("\n"); - return result; +void code_mul(struct node** result, struct node* a, struct node* b) { + if (a->kind != EXPR_INT || b->kind != EXPR_INT) + fill_node_name(result, "mul on non-ints"); + else + fill_node_int(result, *((int*) a->var1) * *((int*) b->var1)); } -expression* code_mul(expression* a, expression* b) { - return (a->kind != EXPR_INT || b->kind != EXPR_INT) - ? make_name_expression("mul on non-ints") - : make_int_expression(*((int*) a->var1) * *((int*) b->var1)); -} - -expression* code_sub(expression* a, expression* b) { - return (a->kind != EXPR_INT || b->kind != EXPR_INT) - ? make_name_expression("sub on non-ints") - : make_int_expression(*((int*) b->var1) - *((int*) a->var1)); +void code_sub(struct node** result, struct node* a, struct node* b) { + if (a->kind != EXPR_INT || b->kind != EXPR_INT) + fill_node_name(result, "sub on non-ints"); + else + fill_node_int(result, *((int*) b->var1) - *((int*) a->var1)); } unsigned char code_find(char* name, void** function) { if (!strcmp(name, "time")) { *function = (void(*)(void)) code_time; return 0; - } else if (!strcmp(name, "print")) { - *function = (void(*)(void)) code_print; - return 1; } else if (!strcmp(name, "mul")) { *function = (void(*)(void)) code_mul; return 2; diff --git a/interpreter/code.h b/interpreter/code.h index 4c850a2..d139fb1 100644 --- a/interpreter/code.h +++ b/interpreter/code.h @@ -2,11 +2,15 @@ #define _H_CODE #include "syntax.h" +#include "graphs.h" -typedef expression* (Code_0) (); -typedef expression* (Code_1) (expression*); -typedef expression* (Code_2) (expression*, expression*); +typedef void (Code_0) (struct node**); +typedef void (Code_1) (struct node**, struct node*); +typedef void (Code_2) (struct node**, struct node*, struct node*); unsigned char code_find(char* name, void** function); +void code_mul(struct node** result, struct node* a, struct node* b); +void code_sub(struct node** result, struct node* a, struct node* b); + #endif diff --git a/interpreter/eval.c b/interpreter/eval.c index 20330cc..8949841 100644 --- a/interpreter/eval.c +++ b/interpreter/eval.c @@ -3,20 +3,9 @@ #include <string.h> #include "code.h" +#include "graphs.h" #include "mem.h" -struct node { - expr_kind kind; - void* var1; - void* var2; - unsigned int used_count; -}; - -typedef struct { - unsigned int length; - struct node* nodes[1]; -} nodes_array; - typedef struct { char* name; struct node* node; @@ -28,19 +17,7 @@ typedef struct { } replacements; void eval(fuspel* rules, struct node** node, - replacements** repls, nodes_array** to_free); - -#define eval_rnf(rs, n, repls, tf) eval(rs, n, repls, tf) - -nodes_array* push_node(nodes_array* nodes, struct node* node) { - unsigned int i; - for (i = 0; i < nodes->length && nodes->nodes[i]; i++); - if (nodes->nodes[i]) - nodes = my_realloc(nodes, sizeof(nodes_array) + - 2 * nodes->length * sizeof(*node)); - nodes->nodes[i] = node; - return nodes; -} + replacements** repls, nodes_array** to_free, unsigned to_rnf); replacements* push_repl(replacements* repls, char* name, struct node* node) { unsigned int i; @@ -50,28 +27,48 @@ replacements* push_repl(replacements* repls, char* name, struct node* node) { 2 * repls->length * sizeof(replacement)); repls->replacements[i].name = name; repls->replacements[i].node = node; + repls->replacements[i + 1].name = NULL; + repls->replacements[i + 1].node = NULL; return repls; } -void free_node(struct node* node, unsigned dont_free_first) { - if (!node) +void replace_all(replacements* repls, struct node** node) { + unsigned char i; + unsigned int org_used_count; + unsigned rerun = 1; + + if (!node || !*node) return; - node->used_count--; + while (rerun) { + rerun = 0; - if (node->kind == EXPR_LIST || - node->kind == EXPR_TUPLE || - node->kind == EXPR_APP) { - free_node((struct node*) node->var1, 0); - free_node((struct node*) node->var2, 0); - } + switch ((*node)->kind) { + case EXPR_INT: + case EXPR_CODE: + break; - if (node->used_count == 0) { - if (node->kind == EXPR_INT || node->kind == EXPR_NAME) - my_free(node->var1); + case EXPR_NAME: + for (i = 0; repls->replacements[i].name; i++) { + if (!strcmp(repls->replacements[i].name, + (char*) (*node)->var1)) { + org_used_count = (*node)->used_count; + free_node(*node, 1); + *node = repls->replacements[i].node; + use_node(*node, org_used_count); + rerun = 1; + break; + } + } + break; - if (!dont_free_first) - my_free(node); + case EXPR_LIST: + case EXPR_TUPLE: + case EXPR_APP: + replace_all(repls, (struct node**) &(*node)->var1); + replace_all(repls, (struct node**) &(*node)->var2); + break; + } } } @@ -99,69 +96,12 @@ struct node** flatten_app_args(struct node* from) { return result; } -void cpy_expression_to_node(struct node* dst, expression* src) { - if (!dst || !src) - return; - - dst->kind = src->kind; - switch (src->kind) { - case EXPR_INT: - dst->var1 = my_calloc(1, sizeof(int)); - *((int*) dst->var1) = *((int*) src->var1); - break; - - case EXPR_NAME: - dst->var1 = my_calloc(1, 1 + strlen((char*) src->var1)); - strcpy(dst->var1, src->var1); - break; - - default: - if (src->var1) { - dst->var1 = my_calloc(1, sizeof(struct node)); - cpy_expression_to_node(dst->var1, src->var1); - } - if (src->var2) { - dst->var2 = my_calloc(1, sizeof(struct node)); - cpy_expression_to_node(dst->var2, src->var2); - } - } - - dst->used_count = 1; -} - -void cpy_node_to_expression(expression* dst, struct node* src) { - if (!dst || !src) - return; - - free_expression(dst); - - dst->kind = src->kind; - switch (src->kind) { - case EXPR_INT: - dst->var1 = my_calloc(1, sizeof(int)); - *((int*) dst->var1) = *((int*) src->var1); - break; - - case EXPR_NAME: - dst->var1 = my_calloc(1, 1 + strlen((char*) src->var1)); - strcpy(dst->var1, src->var1); - break; - - default: - if (src->var1) { - dst->var1 = my_calloc(1, sizeof(expression)); - cpy_node_to_expression(dst->var1, src->var1); - } - if (src->var2) { - dst->var2 = my_calloc(1, sizeof(expression)); - cpy_node_to_expression(dst->var2, src->var2); - } - } -} - unsigned match_expr(fuspel* rules, expression* expr, struct node** node, replacements** repls, nodes_array** to_free) { + if (expr->kind != EXPR_NAME) + eval(rules, node, repls, to_free, 1); + switch (expr->kind) { case EXPR_INT: return *((int*) (*node)->var1) == *((int*) expr->var1); @@ -172,19 +112,17 @@ unsigned match_expr(fuspel* rules, expression* expr, struct node** node, case EXPR_LIST: case EXPR_TUPLE: - eval_rnf(rules, node, repls, to_free); - if ((*node)->kind != expr->kind) return 0; *to_free = push_node(*to_free, *node); - if (expr->var1 == NULL) + if (!expr->var1) return (*node)->var1 == NULL; return - match_expr(rules, expr->var1, (*node)->var1, repls, to_free) && - match_expr(rules, expr->var2, (*node)->var2, repls, to_free); + match_expr(rules, expr->var1, (struct node**) &(*node)->var1, repls, to_free) && + match_expr(rules, expr->var2, (struct node**) &(*node)->var2, repls, to_free); default: return 0; @@ -237,11 +175,49 @@ int match_rule(fuspel* rules, rewrite_rule* rule, struct node* node, } } -void eval(fuspel* rules, struct node** node, +unsigned is_code_app(struct node* node) { + for (; node->kind == EXPR_APP; node = node->var1); + return node->kind == EXPR_CODE; +} + +void eval_code_app(fuspel* rules, struct node** node, replacements** repls, nodes_array** to_free) { + struct node *root, **args; + Code_1* f1; + Code_2* f2; + unsigned char i; + + for (root = *node; root->kind == EXPR_APP; root = root->var1); + if (root->kind != EXPR_CODE || !root->var1) + return; + + args = flatten_app_args(*node); + + for (i = 1; i <= *((unsigned char*) root->var2); i++) + eval(rules, &args[i], repls, to_free, 0); + + switch (*((unsigned char*) root->var2)) { + case 1: + f1 = (Code_1*) root->var1; + f1(node, args[1]); + case 2: + f2 = (Code_2*) root->var1; + f2(node, args[1], args[2]); + } + + use_node(*node, 1); + + my_free(args); +} + +void eval(fuspel* rules, struct node** node, + replacements** repls, nodes_array** to_free, unsigned to_rnf) { fuspel* _rules; unsigned rerun; + if (!node || !*node) + return; + if (!*repls) { *repls = my_calloc(1, sizeof(replacements) + 10 * sizeof(replacement)); (*repls)->length = 10; @@ -261,18 +237,42 @@ void eval(fuspel* rules, struct node** node, case EXPR_NAME: case EXPR_APP: + if (is_code_app(*node)) { + eval_code_app(rules, node, repls, to_free); + rerun = 1; + // TODO + break; + } + _rules = rules; while (_rules) { int add_args = match_rule( rules, &_rules->rule, *node, repls, to_free); - if (add_args == 0) { - free_node(*node, 1); - cpy_expression_to_node(*node, &_rules->rule.rhs); + if (add_args >= 0) { + unsigned char j; + struct node** _node = node; + + for (j = 0; j < add_args; j++) + _node = (struct node**) &(*_node)->var1; + + for (j = 0; (*repls)->replacements[j].node; j++) + use_node((*repls)->replacements[j].node, 1); + + free_node(*_node, 0); + cpy_expression_to_node(*_node, &_rules->rule.rhs); + replace_all(*repls, _node); + + for (j = 0; (*repls)->replacements[j].node; j++) + free_node((*repls)->replacements[j].node, 1); + + (*to_free)->nodes[0] = NULL; + (*repls)->replacements[0].name = NULL; + (*repls)->replacements[0].node = NULL; + rerun = 1; break; } - // TODO add args (*to_free)->nodes[0] = NULL; (*repls)->replacements[0].name = NULL; @@ -283,12 +283,17 @@ void eval(fuspel* rules, struct node** node, break; case EXPR_LIST: + if (!(*node)->var1) + break; case EXPR_TUPLE: - eval(rules, (struct node**) &(*node)->var1, repls, to_free); - eval(rules, (struct node**) &(*node)->var2, repls, to_free); + if (to_rnf) + break; + + eval(rules, (struct node**) &(*node)->var1, repls, to_free, to_rnf); + eval(rules, (struct node**) &(*node)->var2, repls, to_free, to_rnf); break; - default: + case EXPR_CODE: //TODO break; } @@ -306,11 +311,11 @@ expression* eval_main(fuspel* rules) { main_node->var1 = my_calloc(1, 5); strcpy(main_node->var1, "main"); - eval(rules, &main_node, repls, to_free); + eval(rules, &main_node, repls, to_free, 0); cpy_node_to_expression(expr, main_node); - free_node(main_node, 0); + free_node(main_node, 1); my_free(*repls); my_free(*to_free); diff --git a/interpreter/graphs.c b/interpreter/graphs.c new file mode 100644 index 0000000..34877a2 --- /dev/null +++ b/interpreter/graphs.c @@ -0,0 +1,134 @@ +#include "graphs.h" + +#include <string.h> + +#include "mem.h" + +void use_node(struct node* node, unsigned int count) { + if (!node) + return; + + node->used_count += count; + + if (node->kind == EXPR_LIST || + node->kind == EXPR_TUPLE || + node->kind == EXPR_APP) { + use_node(node->var1, count); + use_node(node->var2, count); + } +} + +void free_node(struct node* node, unsigned free_first) { + if (!node) + return; + + node->used_count--; + + if (node->kind == EXPR_LIST || + node->kind == EXPR_TUPLE || + node->kind == EXPR_APP) { + free_node((struct node*) node->var1, 1); + free_node((struct node*) node->var2, 1); + } + + if (node->used_count == 0) { + if (node->kind == EXPR_INT || node->kind == EXPR_NAME) + my_free(node->var1); + + if (node->kind == EXPR_CODE) + my_free(node->var2); + + if (free_first) + my_free(node); + } +} + +nodes_array* push_node(nodes_array* nodes, struct node* node) { + unsigned int i; + for (i = 0; i < nodes->length && nodes->nodes[i]; i++); + if (nodes->nodes[i]) + nodes = my_realloc(nodes, sizeof(nodes_array) + + 2 * nodes->length * sizeof(*node)); + nodes->nodes[i] = node; + nodes->nodes[i + 1] = NULL; + return nodes; +} + +void cpy_expression_to_node(struct node* dst, expression* src) { + if (!dst || !src) + return; + + dst->kind = src->kind; + switch (src->kind) { + case EXPR_INT: + dst->var1 = my_calloc(1, sizeof(int)); + *((int*) dst->var1) = *((int*) src->var1); + break; + + case EXPR_NAME: + dst->var1 = my_calloc(1, 1 + strlen((char*) src->var1)); + strcpy(dst->var1, src->var1); + break; + + case EXPR_CODE: + dst->var1 = src->var1; + dst->var2 = my_calloc(1, sizeof(unsigned char)); + *((unsigned char*) dst->var2) = *((unsigned char*) src->var2); + break; + + case EXPR_LIST: + case EXPR_TUPLE: + case EXPR_APP: + dst->var1 = dst->var2 = NULL; + if (src->var1) { + dst->var1 = my_calloc(1, sizeof(struct node)); + cpy_expression_to_node(dst->var1, src->var1); + } + if (src->var2) { + dst->var2 = my_calloc(1, sizeof(struct node)); + cpy_expression_to_node(dst->var2, src->var2); + } + } + + dst->used_count = 1; +} + +void cpy_node_to_expression(expression* dst, struct node* src) { + if (!dst || !src) + return; + + free_expression(dst); + dst->is_strict = 0; + + dst->kind = src->kind; + switch (src->kind) { + case EXPR_INT: + dst->var1 = my_calloc(1, sizeof(int)); + *((int*) dst->var1) = *((int*) src->var1); + break; + + case EXPR_NAME: + dst->var1 = my_calloc(1, 1 + strlen((char*) src->var1)); + strcpy(dst->var1, src->var1); + break; + + case EXPR_CODE: + dst->var1 = src->var1; + dst->var2 = my_calloc(1, sizeof(unsigned char)); + *((unsigned char*) dst->var2) = *((unsigned char*) src->var2); + break; + + case EXPR_LIST: + case EXPR_TUPLE: + case EXPR_APP: + dst->var1 = dst->var2 = NULL; + if (src->var1) { + dst->var1 = my_calloc(1, sizeof(expression)); + cpy_node_to_expression(dst->var1, src->var1); + } + if (src->var2) { + dst->var2 = my_calloc(1, sizeof(expression)); + cpy_node_to_expression(dst->var2, src->var2); + } + } +} diff --git a/interpreter/graphs.h b/interpreter/graphs.h new file mode 100644 index 0000000..07ca663 --- /dev/null +++ b/interpreter/graphs.h @@ -0,0 +1,26 @@ +#ifndef _H_GRAPHS +#define _H_GRAPHS + +#include "syntax.h" + +struct node { + expr_kind kind; + void* var1; + void* var2; + unsigned int used_count; +}; + +typedef struct { + unsigned int length; + struct node* nodes[1]; +} nodes_array; + +void use_node(struct node* node, unsigned int count); +void free_node(struct node* node, unsigned free_first); + +nodes_array* push_node(nodes_array* nodes, struct node* node); + +void cpy_expression_to_node(struct node* dst, expression* src); +void cpy_node_to_expression(expression* dst, struct node* src); + +#endif diff --git a/interpreter/print.c b/interpreter/print.c index d700101..edcedf3 100644 --- a/interpreter/print.c +++ b/interpreter/print.c @@ -3,6 +3,7 @@ #include <stdio.h> #include "log.h" +#include "mem.h" void print_token(token* tk) { char c; @@ -113,3 +114,11 @@ void print_fuspel(fuspel* rules) { print_fuspel(rules->rest); } } + +void print_node(struct node* node) { + expression* e = my_calloc(1, sizeof(expression)); + cpy_node_to_expression(e, node); + print_expression(e); + free_expression(e); + my_free(e); +} diff --git a/interpreter/print.h b/interpreter/print.h index 5909087..544786f 100644 --- a/interpreter/print.h +++ b/interpreter/print.h @@ -2,6 +2,7 @@ #define _H_PRINT #include "syntax.h" +#include "graphs.h" void print_token(token*); void print_token_list(token_list*); @@ -10,4 +11,6 @@ void print_expression(expression*); void print_rewrite_rule(rewrite_rule*); void print_fuspel(fuspel*); +void print_node(struct node*); + #endif |