Add support for environments and recursive evaluation

4 files changed, 243 insertions, 6 deletions

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);
+}