From b8bad3bf5af3261f25780a8cd8b90a659fe29bab Mon Sep 17 00:00:00 2001 From: Bad Diode Date: Wed, 13 Oct 2021 14:19:32 +0200 Subject: Add support for environments and recursive evaluation --- src/bootstrap/environment.c | 106 ++++++++++++++++++++++++++++++++++++++++++ src/bootstrap/errors.c | 12 +++++ src/bootstrap/main.c | 22 +++++++-- src/bootstrap/objects.c | 109 +++++++++++++++++++++++++++++++++++++++++++- 4 files changed, 243 insertions(+), 6 deletions(-) create mode 100644 src/bootstrap/environment.c (limited to 'src/bootstrap') diff --git a/src/bootstrap/environment.c b/src/bootstrap/environment.c new file mode 100644 index 0000000..1bbe844 --- /dev/null +++ b/src/bootstrap/environment.c @@ -0,0 +1,106 @@ +// +// Environment. +// + +typedef struct EnvEntry { + Object *symbol; + Object *value; +} EnvEntry; + +typedef struct Environment { + struct Environment *parent; + EnvEntry *buf; + size_t size; + size_t cap; +} Environment; + +static Environment *global_env; + +#define ENV_BUF_CAP 8 + +Environment * +env_create(Environment *parent) { + Environment *env = malloc(sizeof(Environment)); + env->parent = parent; + env->buf = NULL; + env->size = 0; + env->cap = ENV_BUF_CAP; + return env; +} + +void +env_add_symbol(Environment *env, Object *symbol, Object *value) { + if (symbol->type != OBJ_TYPE_SYMBOL) { + error_push((Error){ + .type = ERR_TYPE_RUNTIME, + .value = ERR_NOT_A_SYMBOL, + .line = 0, + .col = 0, + }); + return; + } + if (env->buf == NULL) { + env->size = 0; + env->cap = ENV_BUF_CAP; + env->buf = malloc(env->cap * sizeof(EnvEntry)); + } else if (env->size == env->cap) { + env->cap *= 2; + env->buf = realloc(env->buf, env->cap * sizeof(EnvEntry)); + } + env->buf[env->size++] = (EnvEntry){symbol, value}; +} + +bool +obj_eq(Object *a, Object* b) { + if (a->type != b->type) { + return false; + } + switch (a->type) { + case OBJ_TYPE_FIXNUM: { + return a->fixnum == b->fixnum; + } break; + case OBJ_TYPE_STRING: { + if (a->string_n != b->string_n) { + return false; + } + for (size_t i = 0; i < a->string_n; i++) { + if (a->string[i] != b->string[i]) { + return false; + } + } + } break; + case OBJ_TYPE_SYMBOL: { + if (a->symbol_n != b->symbol_n) { + return false; + } + for (size_t i = 0; i < a->symbol_n; i++) { + if (a->symbol[i] != b->symbol[i]) { + return false; + } + } + } break; + case OBJ_TYPE_PAIR: { + // TODO: needs evaluation of parameters... + } break; + default: { + return a == b; + } break; + } + return true; +} + +Object * +env_lookup(Environment *env, Object *symbol) { + while (env != NULL) { + for (size_t i = 0; i < env->size; i++) { + EnvEntry entry = env->buf[i]; + if (obj_eq(symbol, entry.symbol)) { + return entry.value; + } + } + env = env->parent; + } + return obj_err; +} + +// TODO: Free env function. diff --git a/src/bootstrap/errors.c b/src/bootstrap/errors.c index 87752e6..c9d9c97 100644 --- a/src/bootstrap/errors.c +++ b/src/bootstrap/errors.c @@ -11,6 +11,12 @@ typedef enum ErrorValue { ERR_NOT_IMPLEMENTED, ERR_EOF_REACHED, ERR_UNKNOWN_TOKEN, + ERR_UNKNOWN_OBJ_TYPE, + ERR_NOT_A_SYMBOL, + ERR_SYMBOL_NOT_FOUND, + ERR_OBJ_NOT_CALLABLE, + ERR_NOT_ENOUGH_ARGS, + ERR_WRONG_ARG_TYPE, } ErrorValue; typedef struct Error { @@ -27,6 +33,12 @@ static const char* error_msgs[] = { [ERR_NOT_IMPLEMENTED] = "error: not implemented", [ERR_EOF_REACHED] = "error: EOF reached", [ERR_UNKNOWN_TOKEN] = "error: unknown token", + [ERR_UNKNOWN_OBJ_TYPE] = "error: can't eval unknown object type", + [ERR_NOT_A_SYMBOL] = "error: object is not a symbol", + [ERR_SYMBOL_NOT_FOUND] = "error: symbol not found", + [ERR_OBJ_NOT_CALLABLE] = "error: object is not callable", + [ERR_NOT_ENOUGH_ARGS] = "error: not enough arguments", + [ERR_WRONG_ARG_TYPE] = "error: wrong argument type", }; #define ERR_MAX_NUMBER 16 diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c index e6155b4..2aa3038 100755 --- a/src/bootstrap/main.c +++ b/src/bootstrap/main.c @@ -12,6 +12,8 @@ #include "objects.c" #include "parser.c" +#define MAKE_SYM(STR) make_symbol((StringView){(STR), sizeof(STR) - 1}) + void init(void) { // Initialize singletons. @@ -19,6 +21,11 @@ init(void) { obj_true = alloc_object(OBJ_TYPE_BOOL); obj_false = alloc_object(OBJ_TYPE_BOOL); obj_err = alloc_object(OBJ_TYPE_ERR); + + // Global environment. + global_env = env_create(NULL); + env_add_symbol(global_env, MAKE_SYM("quote"), make_procedure(proc_quote)); + env_add_symbol(global_env, MAKE_SYM("+"), make_procedure(proc_sum)); } void @@ -41,8 +48,15 @@ process_source(const StringView *source) { free_objects(root); break; } + + // FIXME: Not freeing result or intermediate objects, can leak memory. + Object *result = eval(global_env, root); + printf("AST: "); display(root); printf("\n"); + printf("EVAL: "); + display(result); + printf("\n"); free_objects(root); } @@ -116,9 +130,9 @@ run_file(char *file_name) { Error err = errors[i]; fprintf(stderr, "%s", file_name); if (err.line != 0) { - fprintf(stderr, ":%ld:%ld: ", err.line, err.col); + fprintf(stderr, ":%ld:%ld", err.line, err.col); } - fprintf(stderr, "%s\n", error_msgs[err.value]); + fprintf(stderr, ": %s\n", error_msgs[err.value]); } errors_n = 0; } @@ -158,9 +172,9 @@ run_stdin(void) { Error err = errors[i]; fprintf(stderr, "stdin"); if (err.line != 0) { - fprintf(stderr, ":%ld:%ld: ", err.line, err.col); + fprintf(stderr, ":%ld:%ld", err.line, err.col); } - fprintf(stderr, "%s\n", error_msgs[err.value]); + fprintf(stderr, ": %s\n", error_msgs[err.value]); } errors_n = 0; } diff --git a/src/bootstrap/objects.c b/src/bootstrap/objects.c index 9acbcd9..30827f1 100644 --- a/src/bootstrap/objects.c +++ b/src/bootstrap/objects.c @@ -9,6 +9,8 @@ typedef enum ObjectType { OBJ_TYPE_ERR, } ObjectType; +struct Environment; + typedef struct Object { ObjectType type; union { @@ -34,7 +36,7 @@ typedef struct Object { }; // OBJ_TYPE_PROCEDURE - struct Object *(*proc)(struct Object *args); + struct Object *(*proc)(struct Environment *env, struct Object *args); }; } Object; @@ -66,7 +68,7 @@ make_fixnum(ssize_t num) { } Object * -make_procedure(Object *(*proc)(struct Object *args)) { +make_procedure(Object *(*proc)(struct Environment *, struct Object *args)) { Object *obj = alloc_object(OBJ_TYPE_PROCEDURE); obj->proc = proc; return obj; @@ -195,3 +197,106 @@ display(Object *root) { } return; } + +#include "environment.c" + +Object * +eval(Environment* env, Object *root) { + switch (root->type) { + case OBJ_TYPE_FIXNUM: + case OBJ_TYPE_BOOL: + case OBJ_TYPE_NIL: + case OBJ_TYPE_STRING: { + return root; + } break; + case OBJ_TYPE_SYMBOL: { + Object *val = env_lookup(env, root); + if (val == obj_err) { + error_push((Error){ + .type = ERR_TYPE_RUNTIME, + .value = ERR_SYMBOL_NOT_FOUND, + }); + return obj_err; + } + return val; + } break; + case OBJ_TYPE_PAIR: { + if (root->car->type == OBJ_TYPE_SYMBOL) { + Object *val = env_lookup(env, root->car); + if (val == obj_err) { + error_push((Error){ + .type = ERR_TYPE_RUNTIME, + .value = ERR_SYMBOL_NOT_FOUND, + }); + return obj_err; + } + if (val->type == OBJ_TYPE_PROCEDURE) { + return val->proc(env, root->cdr); + } + error_push((Error){ + .type = ERR_TYPE_RUNTIME, + .value = ERR_OBJ_NOT_CALLABLE, + }); + return obj_err; + } + } break; + default: { + break; + } break; + } + + error_push((Error){ + .type = ERR_TYPE_RUNTIME, + .value = ERR_UNKNOWN_OBJ_TYPE, + }); + return obj_err; +} + +Object * +proc_quote(Environment *env, Object *obj) { + (void)env; + return obj->car; +} + +Object * +proc_sum(Environment *env, Object *obj) { + // First argument. + if (obj == obj_nil) { + error_push((Error){ + .type = ERR_TYPE_RUNTIME, + .value = ERR_NOT_ENOUGH_ARGS, + }); + return obj_err; + } + Object *car = eval(env, obj->car); + if (car == obj_err) { + return obj_err; + } + if (car->type != OBJ_TYPE_FIXNUM) { + error_push((Error){ + .type = ERR_TYPE_RUNTIME, + .value = ERR_WRONG_ARG_TYPE, + }); + return obj_err; + } + + // Traverse the list. + obj = obj->cdr; + ssize_t tot = car->fixnum; + while (obj->type == OBJ_TYPE_PAIR) { + Object *car = eval(env, obj->car); + if (car == obj_err) { + return obj_err; + } + if (car->type != OBJ_TYPE_FIXNUM) { + error_push((Error){ + .type = ERR_TYPE_RUNTIME, + .value = ERR_WRONG_ARG_TYPE, + }); + return obj_err; + } + tot += car->fixnum; + obj = obj->cdr; + } + return make_fixnum(tot); +} -- cgit v1.2.1