diff options
author | Bad Diode <bd@badd10de.dev> | 2021-10-13 14:19:32 +0200 |
---|---|---|
committer | Bad Diode <bd@badd10de.dev> | 2021-10-13 14:19:32 +0200 |
commit | b8bad3bf5af3261f25780a8cd8b90a659fe29bab (patch) | |
tree | eaaa81ed2cd0583d238e6da8649d1825a2ddfad1 /src | |
parent | f834e2d832ed574d4d8d341bce5e0a57a0c66a61 (diff) | |
download | bdl-b8bad3bf5af3261f25780a8cd8b90a659fe29bab.tar.gz bdl-b8bad3bf5af3261f25780a8cd8b90a659fe29bab.zip |
Add support for environments and recursive evaluation
Diffstat (limited to 'src')
-rw-r--r-- | src/bootstrap/environment.c | 106 | ||||
-rw-r--r-- | src/bootstrap/errors.c | 12 | ||||
-rwxr-xr-x | src/bootstrap/main.c | 22 | ||||
-rw-r--r-- | src/bootstrap/objects.c | 109 |
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 @@ | |||
1 | // | ||
2 | // Environment. | ||
3 | // | ||
4 | |||
5 | typedef struct EnvEntry { | ||
6 | Object *symbol; | ||
7 | Object *value; | ||
8 | } EnvEntry; | ||
9 | |||
10 | typedef struct Environment { | ||
11 | struct Environment *parent; | ||
12 | EnvEntry *buf; | ||
13 | size_t size; | ||
14 | size_t cap; | ||
15 | } Environment; | ||
16 | |||
17 | static Environment *global_env; | ||
18 | |||
19 | #define ENV_BUF_CAP 8 | ||
20 | |||
21 | Environment * | ||
22 | env_create(Environment *parent) { | ||
23 | Environment *env = malloc(sizeof(Environment)); | ||
24 | env->parent = parent; | ||
25 | env->buf = NULL; | ||
26 | env->size = 0; | ||
27 | env->cap = ENV_BUF_CAP; | ||
28 | return env; | ||
29 | } | ||
30 | |||
31 | void | ||
32 | env_add_symbol(Environment *env, Object *symbol, Object *value) { | ||
33 | if (symbol->type != OBJ_TYPE_SYMBOL) { | ||
34 | error_push((Error){ | ||
35 | .type = ERR_TYPE_RUNTIME, | ||
36 | .value = ERR_NOT_A_SYMBOL, | ||
37 | .line = 0, | ||
38 | .col = 0, | ||
39 | }); | ||
40 | return; | ||
41 | } | ||
42 | if (env->buf == NULL) { | ||
43 | env->size = 0; | ||
44 | env->cap = ENV_BUF_CAP; | ||
45 | env->buf = malloc(env->cap * sizeof(EnvEntry)); | ||
46 | } else if (env->size == env->cap) { | ||
47 | env->cap *= 2; | ||
48 | env->buf = realloc(env->buf, env->cap * sizeof(EnvEntry)); | ||
49 | } | ||
50 | env->buf[env->size++] = (EnvEntry){symbol, value}; | ||
51 | } | ||
52 | |||
53 | bool | ||
54 | obj_eq(Object *a, Object* b) { | ||
55 | if (a->type != b->type) { | ||
56 | return false; | ||
57 | } | ||
58 | switch (a->type) { | ||
59 | case OBJ_TYPE_FIXNUM: { | ||
60 | return a->fixnum == b->fixnum; | ||
61 | } break; | ||
62 | case OBJ_TYPE_STRING: { | ||
63 | if (a->string_n != b->string_n) { | ||
64 | return false; | ||
65 | } | ||
66 | for (size_t i = 0; i < a->string_n; i++) { | ||
67 | if (a->string[i] != b->string[i]) { | ||
68 | return false; | ||
69 | } | ||
70 | } | ||
71 | } break; | ||
72 | case OBJ_TYPE_SYMBOL: { | ||
73 | if (a->symbol_n != b->symbol_n) { | ||
74 | return false; | ||
75 | } | ||
76 | for (size_t i = 0; i < a->symbol_n; i++) { | ||
77 | if (a->symbol[i] != b->symbol[i]) { | ||
78 | return false; | ||
79 | } | ||
80 | } | ||
81 | } break; | ||
82 | case OBJ_TYPE_PAIR: { | ||
83 | // TODO: needs evaluation of parameters... | ||
84 | } break; | ||
85 | default: { | ||
86 | return a == b; | ||
87 | } break; | ||
88 | } | ||
89 | return true; | ||
90 | } | ||
91 | |||
92 | Object * | ||
93 | env_lookup(Environment *env, Object *symbol) { | ||
94 | while (env != NULL) { | ||
95 | for (size_t i = 0; i < env->size; i++) { | ||
96 | EnvEntry entry = env->buf[i]; | ||
97 | if (obj_eq(symbol, entry.symbol)) { | ||
98 | return entry.value; | ||
99 | } | ||
100 | } | ||
101 | env = env->parent; | ||
102 | } | ||
103 | return obj_err; | ||
104 | } | ||
105 | |||
106 | // 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 { | |||
11 | ERR_NOT_IMPLEMENTED, | 11 | ERR_NOT_IMPLEMENTED, |
12 | ERR_EOF_REACHED, | 12 | ERR_EOF_REACHED, |
13 | ERR_UNKNOWN_TOKEN, | 13 | ERR_UNKNOWN_TOKEN, |
14 | ERR_UNKNOWN_OBJ_TYPE, | ||
15 | ERR_NOT_A_SYMBOL, | ||
16 | ERR_SYMBOL_NOT_FOUND, | ||
17 | ERR_OBJ_NOT_CALLABLE, | ||
18 | ERR_NOT_ENOUGH_ARGS, | ||
19 | ERR_WRONG_ARG_TYPE, | ||
14 | } ErrorValue; | 20 | } ErrorValue; |
15 | 21 | ||
16 | typedef struct Error { | 22 | typedef struct Error { |
@@ -27,6 +33,12 @@ static const char* error_msgs[] = { | |||
27 | [ERR_NOT_IMPLEMENTED] = "error: not implemented", | 33 | [ERR_NOT_IMPLEMENTED] = "error: not implemented", |
28 | [ERR_EOF_REACHED] = "error: EOF reached", | 34 | [ERR_EOF_REACHED] = "error: EOF reached", |
29 | [ERR_UNKNOWN_TOKEN] = "error: unknown token", | 35 | [ERR_UNKNOWN_TOKEN] = "error: unknown token", |
36 | [ERR_UNKNOWN_OBJ_TYPE] = "error: can't eval unknown object type", | ||
37 | [ERR_NOT_A_SYMBOL] = "error: object is not a symbol", | ||
38 | [ERR_SYMBOL_NOT_FOUND] = "error: symbol not found", | ||
39 | [ERR_OBJ_NOT_CALLABLE] = "error: object is not callable", | ||
40 | [ERR_NOT_ENOUGH_ARGS] = "error: not enough arguments", | ||
41 | [ERR_WRONG_ARG_TYPE] = "error: wrong argument type", | ||
30 | }; | 42 | }; |
31 | 43 | ||
32 | #define ERR_MAX_NUMBER 16 | 44 | #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 @@ | |||
12 | #include "objects.c" | 12 | #include "objects.c" |
13 | #include "parser.c" | 13 | #include "parser.c" |
14 | 14 | ||
15 | #define MAKE_SYM(STR) make_symbol((StringView){(STR), sizeof(STR) - 1}) | ||
16 | |||
15 | void | 17 | void |
16 | init(void) { | 18 | init(void) { |
17 | // Initialize singletons. | 19 | // Initialize singletons. |
@@ -19,6 +21,11 @@ init(void) { | |||
19 | obj_true = alloc_object(OBJ_TYPE_BOOL); | 21 | obj_true = alloc_object(OBJ_TYPE_BOOL); |
20 | obj_false = alloc_object(OBJ_TYPE_BOOL); | 22 | obj_false = alloc_object(OBJ_TYPE_BOOL); |
21 | obj_err = alloc_object(OBJ_TYPE_ERR); | 23 | obj_err = alloc_object(OBJ_TYPE_ERR); |
24 | |||
25 | // Global environment. | ||
26 | global_env = env_create(NULL); | ||
27 | env_add_symbol(global_env, MAKE_SYM("quote"), make_procedure(proc_quote)); | ||
28 | env_add_symbol(global_env, MAKE_SYM("+"), make_procedure(proc_sum)); | ||
22 | } | 29 | } |
23 | 30 | ||
24 | void | 31 | void |
@@ -41,8 +48,15 @@ process_source(const StringView *source) { | |||
41 | free_objects(root); | 48 | free_objects(root); |
42 | break; | 49 | break; |
43 | } | 50 | } |
51 | |||
52 | // FIXME: Not freeing result or intermediate objects, can leak memory. | ||
53 | Object *result = eval(global_env, root); | ||
54 | printf("AST: "); | ||
44 | display(root); | 55 | display(root); |
45 | printf("\n"); | 56 | printf("\n"); |
57 | printf("EVAL: "); | ||
58 | display(result); | ||
59 | printf("\n"); | ||
46 | free_objects(root); | 60 | free_objects(root); |
47 | } | 61 | } |
48 | 62 | ||
@@ -116,9 +130,9 @@ run_file(char *file_name) { | |||
116 | Error err = errors[i]; | 130 | Error err = errors[i]; |
117 | fprintf(stderr, "%s", file_name); | 131 | fprintf(stderr, "%s", file_name); |
118 | if (err.line != 0) { | 132 | if (err.line != 0) { |
119 | fprintf(stderr, ":%ld:%ld: ", err.line, err.col); | 133 | fprintf(stderr, ":%ld:%ld", err.line, err.col); |
120 | } | 134 | } |
121 | fprintf(stderr, "%s\n", error_msgs[err.value]); | 135 | fprintf(stderr, ": %s\n", error_msgs[err.value]); |
122 | } | 136 | } |
123 | errors_n = 0; | 137 | errors_n = 0; |
124 | } | 138 | } |
@@ -158,9 +172,9 @@ run_stdin(void) { | |||
158 | Error err = errors[i]; | 172 | Error err = errors[i]; |
159 | fprintf(stderr, "stdin"); | 173 | fprintf(stderr, "stdin"); |
160 | if (err.line != 0) { | 174 | if (err.line != 0) { |
161 | fprintf(stderr, ":%ld:%ld: ", err.line, err.col); | 175 | fprintf(stderr, ":%ld:%ld", err.line, err.col); |
162 | } | 176 | } |
163 | fprintf(stderr, "%s\n", error_msgs[err.value]); | 177 | fprintf(stderr, ": %s\n", error_msgs[err.value]); |
164 | } | 178 | } |
165 | errors_n = 0; | 179 | errors_n = 0; |
166 | } | 180 | } |
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 { | |||
9 | OBJ_TYPE_ERR, | 9 | OBJ_TYPE_ERR, |
10 | } ObjectType; | 10 | } ObjectType; |
11 | 11 | ||
12 | struct Environment; | ||
13 | |||
12 | typedef struct Object { | 14 | typedef struct Object { |
13 | ObjectType type; | 15 | ObjectType type; |
14 | union { | 16 | union { |
@@ -34,7 +36,7 @@ typedef struct Object { | |||
34 | }; | 36 | }; |
35 | 37 | ||
36 | // OBJ_TYPE_PROCEDURE | 38 | // OBJ_TYPE_PROCEDURE |
37 | struct Object *(*proc)(struct Object *args); | 39 | struct Object *(*proc)(struct Environment *env, struct Object *args); |
38 | }; | 40 | }; |
39 | } Object; | 41 | } Object; |
40 | 42 | ||
@@ -66,7 +68,7 @@ make_fixnum(ssize_t num) { | |||
66 | } | 68 | } |
67 | 69 | ||
68 | Object * | 70 | Object * |
69 | make_procedure(Object *(*proc)(struct Object *args)) { | 71 | make_procedure(Object *(*proc)(struct Environment *, struct Object *args)) { |
70 | Object *obj = alloc_object(OBJ_TYPE_PROCEDURE); | 72 | Object *obj = alloc_object(OBJ_TYPE_PROCEDURE); |
71 | obj->proc = proc; | 73 | obj->proc = proc; |
72 | return obj; | 74 | return obj; |
@@ -195,3 +197,106 @@ display(Object *root) { | |||
195 | } | 197 | } |
196 | return; | 198 | return; |
197 | } | 199 | } |
200 | |||
201 | #include "environment.c" | ||
202 | |||
203 | Object * | ||
204 | eval(Environment* env, Object *root) { | ||
205 | switch (root->type) { | ||
206 | case OBJ_TYPE_FIXNUM: | ||
207 | case OBJ_TYPE_BOOL: | ||
208 | case OBJ_TYPE_NIL: | ||
209 | case OBJ_TYPE_STRING: { | ||
210 | return root; | ||
211 | } break; | ||
212 | case OBJ_TYPE_SYMBOL: { | ||
213 | Object *val = env_lookup(env, root); | ||
214 | if (val == obj_err) { | ||
215 | error_push((Error){ | ||
216 | .type = ERR_TYPE_RUNTIME, | ||
217 | .value = ERR_SYMBOL_NOT_FOUND, | ||
218 | }); | ||
219 | return obj_err; | ||
220 | } | ||
221 | return val; | ||
222 | } break; | ||
223 | case OBJ_TYPE_PAIR: { | ||
224 | if (root->car->type == OBJ_TYPE_SYMBOL) { | ||
225 | Object *val = env_lookup(env, root->car); | ||
226 | if (val == obj_err) { | ||
227 | error_push((Error){ | ||
228 | .type = ERR_TYPE_RUNTIME, | ||
229 | .value = ERR_SYMBOL_NOT_FOUND, | ||
230 | }); | ||
231 | return obj_err; | ||
232 | } | ||
233 | if (val->type == OBJ_TYPE_PROCEDURE) { | ||
234 | return val->proc(env, root->cdr); | ||
235 | } | ||
236 | error_push((Error){ | ||
237 | .type = ERR_TYPE_RUNTIME, | ||
238 | .value = ERR_OBJ_NOT_CALLABLE, | ||
239 | }); | ||
240 | return obj_err; | ||
241 | } | ||
242 | } break; | ||
243 | default: { | ||
244 | break; | ||
245 | } break; | ||
246 | } | ||
247 | |||
248 | error_push((Error){ | ||
249 | .type = ERR_TYPE_RUNTIME, | ||
250 | .value = ERR_UNKNOWN_OBJ_TYPE, | ||
251 | }); | ||
252 | return obj_err; | ||
253 | } | ||
254 | |||
255 | Object * | ||
256 | proc_quote(Environment *env, Object *obj) { | ||
257 | (void)env; | ||
258 | return obj->car; | ||
259 | } | ||
260 | |||
261 | Object * | ||
262 | proc_sum(Environment *env, Object *obj) { | ||
263 | // First argument. | ||
264 | if (obj == obj_nil) { | ||
265 | error_push((Error){ | ||
266 | .type = ERR_TYPE_RUNTIME, | ||
267 | .value = ERR_NOT_ENOUGH_ARGS, | ||
268 | }); | ||
269 | return obj_err; | ||
270 | } | ||
271 | Object *car = eval(env, obj->car); | ||
272 | if (car == obj_err) { | ||
273 | return obj_err; | ||
274 | } | ||
275 | if (car->type != OBJ_TYPE_FIXNUM) { | ||
276 | error_push((Error){ | ||
277 | .type = ERR_TYPE_RUNTIME, | ||
278 | .value = ERR_WRONG_ARG_TYPE, | ||
279 | }); | ||
280 | return obj_err; | ||
281 | } | ||
282 | |||
283 | // Traverse the list. | ||
284 | obj = obj->cdr; | ||
285 | ssize_t tot = car->fixnum; | ||
286 | while (obj->type == OBJ_TYPE_PAIR) { | ||
287 | Object *car = eval(env, obj->car); | ||
288 | if (car == obj_err) { | ||
289 | return obj_err; | ||
290 | } | ||
291 | if (car->type != OBJ_TYPE_FIXNUM) { | ||
292 | error_push((Error){ | ||
293 | .type = ERR_TYPE_RUNTIME, | ||
294 | .value = ERR_WRONG_ARG_TYPE, | ||
295 | }); | ||
296 | return obj_err; | ||
297 | } | ||
298 | tot += car->fixnum; | ||
299 | obj = obj->cdr; | ||
300 | } | ||
301 | return make_fixnum(tot); | ||
302 | } | ||