From 970c0ac9321eff3f45af3b2cbf3785c204d5315a Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Mon, 28 Dec 2015 18:37:50 -0500 Subject: [PATCH] Finished anf transformation --- Makefile | 3 +- source/anf.c | 133 +++++++++++++++++++++++++++++++++++++++++++++++++ source/main.c | 118 ------------------------------------------- source/sclpl.h | 3 ++ 4 files changed, 138 insertions(+), 119 deletions(-) create mode 100644 source/anf.c diff --git a/Makefile b/Makefile index c6fe2cf..56d89fc 100644 --- a/Makefile +++ b/Makefile @@ -22,7 +22,8 @@ OBJS = source/main.o \ source/pprint.o \ source/gc.o \ source/vec.o \ - source/ast.o + source/ast.o \ + source/anf.o all: options sclpl test diff --git a/source/anf.c b/source/anf.c new file mode 100644 index 0000000..2f3e8c5 --- /dev/null +++ b/source/anf.c @@ -0,0 +1,133 @@ +#include + +static bool isatomic(AST* tree) +{ + switch (tree->type) { + case AST_STRING: + case AST_SYMBOL: + case AST_IDENT: + case AST_CHAR: + case AST_INT: + case AST_FLOAT: + case AST_BOOL: + case AST_FUNC: + return true; + default: + return false; + } +} + +static bool isconst(AST* tree) { + bool ret = isatomic(tree); + if (!ret) { + if (tree->type == AST_FNAPP) { + ret = isatomic(fnapp_fn(tree)); + for (int i = 0; i < vec_size(fnapp_args(tree)); i++) { + ret = ret && isatomic(vec_at(fnapp_args(tree), i)); + } + } else if (tree->type == AST_IF) { + ret = isatomic(ifexpr_cond(tree)); + } + } + return ret; +} + +static AST* normalize_def(AST* tree) +{ + Tok name = { .value.text = def_name(tree) }; + return Def(&name, normalize(def_value(tree))); +} + +static AST* normalize_fnapp(AST* tree) +{ + AST* normalized = tree; + AST* fn = fnapp_fn(tree); + /* Normalize the function */ + if (!isatomic(fn)) { + AST* temp = TempVar(); + fnapp_set_fn(tree, temp); + normalized = Let(temp, fn, tree); + } + /* Normalize the function arguments */ + vec_t temps; + vec_init(&temps); + vec_t* args = fnapp_args(tree); + for (int i = 0; i < vec_size(args); i++) { + AST* arg = (AST*)vec_at(args, i); + if (!isatomic(arg)) { + AST* temp = TempVar(); + vec_push_back(&temps, Let(temp, arg, NULL)); + vec_set(args, i, temp); + } + } + /* Nest all the scopes and return the new form */ + for (int i = vec_size(&temps); i > 0; i--) { + AST* let = (AST*)vec_at(&temps,i-1); + let_set_body(let, normalized); + normalized = let; + } + vec_deinit(&temps); + return normalized; +} + +static AST* normalize_if(AST* tree) +{ + AST* cond = normalize(ifexpr_cond(tree)); + AST* thenbr = normalize(ifexpr_then(tree)); + AST* elsebr = normalize(ifexpr_else(tree)); + if (!isatomic(cond)) { + AST* temp = TempVar(); + AST* body = IfExpr(); //(temp, thenbr, elsebr); + ifexpr_set_cond(body, temp); + ifexpr_set_then(body, thenbr); + ifexpr_set_else(body, elsebr); + tree = Let(temp, cond, body); + } else { + tree = IfExpr(); //(cond, thenbr, elsebr); + ifexpr_set_cond(tree, cond); + ifexpr_set_then(tree, thenbr); + ifexpr_set_else(tree, elsebr); + } + return tree; +} + +static AST* normalize_func(AST* tree) +{ + func_set_body(tree, normalize(func_body(tree))); + return tree; +} + +static AST* normalize_let(AST* tree) +{ + AST* var = let_var(tree); + AST* val = normalize(let_val(tree)); + AST* body = normalize(let_body(tree)); + /* Find the inner most let block */ + if (!isconst(val)) { + AST* let = val; + while (let->type == AST_LET && let_body(let)->type == AST_LET) + let = let_body(let); + let_set_body(let, Let(var, let_body(let), body)); + tree = let; + } else { + tree = Let(var, val, body); + } + return tree; +} + +AST* normalize(AST* tree) +{ + if (NULL == tree) + return tree; + switch (tree->type) + { + case AST_DEF: tree = normalize_def(tree); break; + case AST_FNAPP: tree = normalize_fnapp(tree); break; + case AST_IF: tree = normalize_if(tree); break; + case AST_FUNC: tree = normalize_func(tree); break; + case AST_LET: tree = normalize_let(tree); break; + default: break; + } + return tree; +} + diff --git a/source/main.c b/source/main.c index 19f45b9..8af8530 100644 --- a/source/main.c +++ b/source/main.c @@ -4,124 +4,6 @@ char* ARGV0; bool Verbose = false; char* Artifact = "bin"; -AST* normalize(AST* tree); - -bool isatomic(AST* tree) -{ - switch (tree->type) { - case AST_STRING: - case AST_SYMBOL: - case AST_IDENT: - case AST_CHAR: - case AST_INT: - case AST_FLOAT: - case AST_BOOL: - case AST_FUNC: - return true; - default: - return false; - } -} - -AST* normalize_def(AST* tree) -{ - Tok name = { .value.text = def_name(tree) }; - return Def(&name, normalize(def_value(tree))); -} - -AST* normalize_fnapp(AST* tree) -{ - AST* normalized = tree; - AST* fn = fnapp_fn(tree); - /* Normalize the function */ - if (!isatomic(fn)) { - AST* temp = TempVar(); - fnapp_set_fn(tree, temp); - normalized = Let(temp, fn, tree); - } - /* Normalize the function arguments */ - vec_t temps; - vec_init(&temps); - vec_t* args = fnapp_args(tree); - for (int i = 0; i < vec_size(args); i++) { - AST* arg = (AST*)vec_at(args, i); - if (!isatomic(arg)) { - AST* temp = TempVar(); - vec_push_back(&temps, Let(temp, arg, NULL)); - vec_set(args, i, temp); - } - } - /* Nest all the scopes and return the new form */ - for (int i = vec_size(&temps); i > 0; i--) { - AST* let = (AST*)vec_at(&temps,i-1); - let_set_body(let, normalized); - normalized = let; - } - vec_deinit(&temps); - return normalized; -} - -AST* normalize_if(AST* tree) -{ - AST* cond = normalize(ifexpr_cond(tree)); - AST* thenbr = normalize(ifexpr_then(tree)); - AST* elsebr = normalize(ifexpr_else(tree)); - if (!isatomic(cond)) { - AST* temp = TempVar(); - AST* body = IfExpr(); //(temp, thenbr, elsebr); - ifexpr_set_cond(body, temp); - ifexpr_set_then(body, thenbr); - ifexpr_set_else(body, elsebr); - tree = Let(temp, cond, body); - } else { - tree = IfExpr(); //(cond, thenbr, elsebr); - ifexpr_set_cond(tree, cond); - ifexpr_set_then(tree, thenbr); - ifexpr_set_else(tree, elsebr); - } - return tree; -} - -AST* normalize_func(AST* tree) -{ - func_set_body(tree, normalize(func_body(tree))); - return tree; -} - -AST* normalize_let(AST* tree) -{ - AST* var = let_var(tree); - AST* val = normalize(let_val(tree)); - AST* body = normalize(let_body(tree)); - /* Find the inner most let block */ - if (!isatomic(val)) { - AST* let = val; - while (let->type == AST_LET && let_body(let)->type == AST_LET) - let = let_body(let); - let_set_body(let, Let(var, let_body(let), body)); - tree = let; - } else { - tree = Let(var, val, body); - } - return tree; -} - -AST* normalize(AST* tree) -{ - if (NULL == tree) - return tree; - switch (tree->type) - { - case AST_DEF: tree = normalize_def(tree); break; - case AST_FNAPP: tree = normalize_fnapp(tree); break; - case AST_IF: tree = normalize_if(tree); break; - case AST_FUNC: tree = normalize_func(tree); break; - case AST_LET: tree = normalize_let(tree); break; - default: break; - } - return tree; -} - /* Driver Modes *****************************************************************************/ static int emit_tokens(void) { diff --git a/source/sclpl.h b/source/sclpl.h index 9ddc8d8..1a2282e 100644 --- a/source/sclpl.h +++ b/source/sclpl.h @@ -212,6 +212,9 @@ Parser* parser_new(char* p_prompt, FILE* input); // Grammar Routines AST* toplevel(Parser* p); +// Compiler Passes +AST* normalize(AST* tree); + /* Pretty Printing *****************************************************************************/ void pprint_token_type(FILE* file, Tok* token); -- 2.49.0