aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorBad Diode <bd@badd10de.dev>2022-02-01 18:36:52 +0100
committerBad Diode <bd@badd10de.dev>2022-02-01 18:36:52 +0100
commitee1a5de91c875fb66724dc21c02333bfebe2a812 (patch)
treed3eaa226816d295bb9dc48a2aed27044832ec413 /src
parent3156265c7b2da8cc43fee996c0518ea274d39c8a (diff)
downloadbdl-ee1a5de91c875fb66724dc21c02333bfebe2a812.tar.gz
bdl-ee1a5de91c875fb66724dc21c02333bfebe2a812.zip
Add new syntax to lexer and prepare refactor
Diffstat (limited to 'src')
-rw-r--r--src/bytecode/chunk.c47
-rwxr-xr-xsrc/bytecode/chunk.h36
-rwxr-xr-xsrc/bytecode/compiler.h748
-rwxr-xr-xsrc/bytecode/darray.h81
-rwxr-xr-xsrc/bytecode/debug.h105
-rwxr-xr-xsrc/bytecode/errors.c52
-rwxr-xr-xsrc/bytecode/errors.h46
-rw-r--r--src/bytecode/hashtable.h208
-rwxr-xr-xsrc/bytecode/lexer.c294
-rwxr-xr-xsrc/bytecode/lexer.h92
-rwxr-xr-xsrc/bytecode/main.c214
-rw-r--r--src/bytecode/objects.c151
-rwxr-xr-xsrc/bytecode/objects.h80
-rwxr-xr-xsrc/bytecode/ops.h46
-rwxr-xr-xsrc/bytecode/read_line.c32
-rwxr-xr-xsrc/bytecode/read_line.h10
-rwxr-xr-xsrc/bytecode/string_view.c40
-rwxr-xr-xsrc/bytecode/string_view.h23
-rwxr-xr-xsrc/bytecode/types.h30
-rwxr-xr-xsrc/bytecode/vm.h396
-rw-r--r--src/errors.c62
-rw-r--r--src/errors.h30
-rw-r--r--src/lexer.c224
-rw-r--r--src/lexer.h23
-rw-r--r--src/main.c56
-rw-r--r--src/string_view.c9
-rw-r--r--src/string_view.h3
-rw-r--r--src/treewalk/darray.h78
-rw-r--r--src/treewalk/environment.c72
-rw-r--r--src/treewalk/environment.h27
-rw-r--r--src/treewalk/errors.c29
-rw-r--r--src/treewalk/errors.h38
-rw-r--r--src/treewalk/gc.c199
-rw-r--r--src/treewalk/gc.h46
-rw-r--r--src/treewalk/hashtable.h191
-rw-r--r--src/treewalk/lexer.c257
-rw-r--r--src/treewalk/lexer.h57
-rwxr-xr-xsrc/treewalk/main.c288
-rw-r--r--src/treewalk/objects.c141
-rw-r--r--src/treewalk/objects.h75
-rw-r--r--src/treewalk/parser.c139
-rw-r--r--src/treewalk/parser.h22
-rw-r--r--src/treewalk/primitives.c918
-rw-r--r--src/treewalk/primitives.h60
-rw-r--r--src/treewalk/read_line.c32
-rw-r--r--src/treewalk/read_line.h10
-rw-r--r--src/treewalk/singletons.c17
-rw-r--r--src/treewalk/string_view.c40
-rw-r--r--src/treewalk/string_view.h21
-rw-r--r--src/x86_64/postlude.asm12
-rw-r--r--src/x86_64/prelude.asm134
51 files changed, 237 insertions, 5804 deletions
diff --git a/src/bytecode/chunk.c b/src/bytecode/chunk.c
deleted file mode 100644
index af4a3a2..0000000
--- a/src/bytecode/chunk.c
+++ /dev/null
@@ -1,47 +0,0 @@
1#include "chunk.h"
2#include "objects.h"
3
4Chunk *
5chunk_init(StringView name) {
6 Chunk *chunk = malloc(sizeof(Chunk));
7 array_init(chunk->code, 0);
8 array_init(chunk->constants, 0);
9 array_init(chunk->lines, 0);
10 array_init(chunk->name, name.n);
11 array_insert(chunk->name, name.start, name.n);
12 chunk->n_params = 0;
13 chunk->n_locals = 0;
14 return chunk;
15}
16
17void
18chunk_free(Chunk *chunk) {
19 array_free(chunk->code);
20 for (size_t i = 0; i < array_size(chunk->constants); i++) {
21 Object obj = chunk->constants[i];
22 object_free(&obj);
23 }
24 array_free(chunk->constants);
25 array_free(chunk->lines);
26 array_free(chunk->name);
27 free(chunk);
28}
29
30void
31add_code(Chunk *chunk, u8 byte, size_t line, size_t col) {
32 array_push(chunk->code, byte);
33 LineInfo info = (LineInfo){line, col};
34 array_push(chunk->lines, info);
35}
36
37size_t
38add_constant(Chunk *chunk, Object obj) {
39 size_t pos = array_size(chunk->constants);
40 for (size_t i = 0; i < pos; i++) {
41 if (object_equal(obj, chunk->constants[i])) {
42 return i;
43 }
44 }
45 array_push(chunk->constants, obj);
46 return pos;
47}
diff --git a/src/bytecode/chunk.h b/src/bytecode/chunk.h
deleted file mode 100755
index 9457fa9..0000000
--- a/src/bytecode/chunk.h
+++ /dev/null
@@ -1,36 +0,0 @@
1#ifndef BDL_CHUNK_H
2#define BDL_CHUNK_H
3
4#include "darray.h"
5#include "string_view.h"
6
7typedef struct Object Object;
8
9typedef struct LineInfo {
10 size_t line;
11 size_t col;
12} LineInfo;
13
14typedef struct Chunk {
15 // Program code.
16 u8 *code;
17 // Compile time constants.
18 Object *constants;
19 // Contains debugging information for every code operation.
20 LineInfo *lines;
21 // Chunk name.
22 char *name;
23
24 // Number of locals and parameters.
25 size_t n_params;
26 size_t n_locals;
27} Chunk;
28
29#define NEW_CHUNK(NAME) chunk_init((StringView){(NAME), sizeof(NAME) - 1})
30
31Chunk * chunk_init(StringView name);
32void add_code(Chunk *chunk, u8 byte, size_t line, size_t col);
33size_t add_constant(Chunk *chunk, Object obj);
34void chunk_free(Chunk *chunk);
35
36#endif // BDL_CHUNK_H
diff --git a/src/bytecode/compiler.h b/src/bytecode/compiler.h
deleted file mode 100755
index 5f38216..0000000
--- a/src/bytecode/compiler.h
+++ /dev/null
@@ -1,748 +0,0 @@
1#ifndef BDL_COMPILER_H
2#define BDL_COMPILER_H
3
4#include "chunk.h"
5#include "lexer.h"
6
7#define MAX_DEPTH 1024
8
9typedef struct Scope {
10 StringView *params;
11 StringView *locals;
12 Token *captured;
13} Scope;
14
15typedef struct Compiler {
16 Token *tokens;
17 size_t current;
18 size_t scope_depth;
19 Scope scopes[MAX_DEPTH];
20} Compiler;
21
22
23// Mimics the functionality in the Scanner functions, but for entire tokens.
24Token next_token(Compiler *compiler);
25Token peek_token(const Compiler *compiler);
26bool has_next_token(const Compiler *compiler);
27
28// Scope initialization/exit.
29void enter_scope(Compiler *compiler);
30void exit_scope(Compiler *compiler);
31
32void
33enter_scope(Compiler *compiler) {
34 Scope *scope = &compiler->scopes[compiler->scope_depth++];
35 array_init(scope->params, 0);
36 array_init(scope->locals, 0);
37 array_init(scope->captured, 0);
38}
39
40void
41exit_scope(Compiler *compiler) {
42 Scope *scope = &compiler->scopes[--compiler->scope_depth];
43 array_free(scope->params);
44 array_free(scope->locals);
45 array_free(scope->captured);
46}
47
48Scope *
49get_current_scope(Compiler *compiler) {
50 return &compiler->scopes[compiler->scope_depth - 1];
51}
52
53Chunk * compile(Token *tokens);
54
55Token
56peek_token(const Compiler *compiler) {
57 return compiler->tokens[compiler->current];
58}
59
60Token
61next_token(Compiler *compiler) {
62 return compiler->tokens[compiler->current++];
63}
64
65bool
66has_next_token(const Compiler *compiler) {
67 return compiler->current < array_size(compiler->tokens);
68}
69
70ssize_t
71find_local_index(Scope *scope, Token tok) {
72 for (size_t i = 0; i < array_size(scope->locals); i++) {
73 if (sv_equal(&tok.value, &scope->locals[i])) {
74 return i;
75 }
76 }
77 return -1;
78}
79
80ssize_t
81find_captued_index(Scope *scope, Token tok) {
82 for (size_t i = 0; i < array_size(scope->captured); i++) {
83 if (sv_equal(&tok.value, &scope->captured[i].value)) {
84 return i;
85 }
86 }
87 return -1;
88}
89
90void
91emit_constant(Chunk *chunk, Token tok, Object obj) {
92 size_t prev_size = array_size(chunk->constants);
93 size_t num_idx = add_constant(chunk, obj);
94 add_code(chunk, OP_CONSTANT, tok.line, tok.column);
95 add_code(chunk, num_idx, tok.line, tok.column);
96
97 // If the non value constant was already present we need to properly free
98 // the memory from the object given to this function.
99 if (prev_size == array_size(chunk->constants)) {
100 object_free(&obj);
101 }
102}
103
104size_t
105emit_jump(Chunk *chunk, Token tok, Ops op, ssize_t offset) {
106 add_code(chunk, op, tok.line, tok.column);
107 add_code(chunk, ((u16)offset >> 8) & 0xFF, tok.line, tok.column);
108 add_code(chunk, ((u16)offset) & 0xFF, tok.line, tok.column);
109 return array_size(chunk->code) - 2;
110}
111
112void
113patch_jump(Chunk *chunk, ssize_t offset) {
114 ssize_t jump = array_size(chunk->code) - offset - 2;
115 assert((u16)jump <= UINT16_MAX && "error: jump is too long");
116 chunk->code[offset] = ((u16)jump >> 8) & 0xFF;
117 chunk->code[offset + 1] = ((u16)jump) & 0xFF;
118}
119
120void
121parse_fixnum(Chunk *chunk, Token tok) {
122 ssize_t num = 0;
123 int sign = 1;
124 for (size_t i = 0; i < tok.value.n; i++) {
125 char c = tok.value.start[i];
126 if (c == '-') {
127 sign = -1;
128 continue;
129 }
130 num = num * 10 + (c - '0');
131 }
132 emit_constant(chunk, tok, FIXNUM_VAL(num * sign));
133}
134
135void
136parse_symbol(Chunk *chunk, Compiler *compiler, Token tok) {
137 if (compiler->scope_depth > 1) {
138 Scope *current_scope = get_current_scope(compiler);
139 ssize_t idx = -1;
140 // Check if the variable was already captured.
141 idx = find_captued_index(current_scope, tok);
142 if (idx >= 0) {
143 emit_constant(chunk, tok, FIXNUM_VAL(idx));
144 add_code(chunk, OP_CAPTURED, tok.line, tok.column);
145 return;
146 }
147
148 // Check current scope locals. If we find it, emit OP_LOCAL.
149 idx = find_local_index(current_scope, tok);
150 if (idx >= 0) {
151 emit_constant(chunk, tok, FIXNUM_VAL(idx));
152 add_code(chunk, OP_LOCAL, tok.line, tok.column);
153 return;
154 }
155
156 // Descend scopes, if we find the symbol at a different depth,
157 // we need to capture the variable.
158 size_t depth = compiler->scope_depth - 2;
159 while (depth > 0) {
160 Scope *scope = &compiler->scopes[depth];
161 idx = find_local_index(scope, tok);
162 if (idx >= 0) {
163 // Put captured variable on stack.
164 ssize_t captured_idx = array_size(current_scope->captured);
165 emit_constant(chunk, tok, FIXNUM_VAL(captured_idx));
166 add_code(chunk, OP_CAPTURED, tok.line, tok.column);
167 array_push(current_scope->captured, tok);
168 return;
169 }
170 depth--;
171 }
172
173 // TODO: Capture globals?
174 }
175
176 Object obj = make_symbol(tok.value);
177 emit_constant(chunk, tok, obj);
178 add_code(chunk, OP_GET, tok.line, tok.column);
179}
180
181void parse_tree(Chunk *chunk, Compiler *compiler);
182
183void
184compile_list_binary_op(Chunk *chunk, Compiler *compiler, Token start, Ops op) {
185 size_t n = 0;
186 while (has_next_token(compiler)) {
187 Token tok = peek_token(compiler);
188 if (tok.type == TOKEN_EOF) {
189 error_push((Error){
190 .type = ERR_TYPE_COMPILER,
191 .value = ERR_UNBALANCED_PAREN,
192 .line = start.line,
193 .col = start.column,
194 });
195 return;
196 }
197 if (tok.type == TOKEN_RPAREN) {
198 next_token(compiler);
199 if (n <= 1) {
200 error_push((Error){
201 .type = ERR_TYPE_COMPILER,
202 .value = ERR_NOT_ENOUGH_ARGS,
203 .line = start.line,
204 .col = start.column,
205 });
206 return;
207 }
208 break;
209 }
210 parse_tree(chunk, compiler);
211 n++;
212 }
213 emit_constant(chunk, start, FIXNUM_VAL(n));
214 add_code(chunk, op, start.line, start.column);
215}
216
217void
218compile_list_unary_op(Chunk *chunk, Compiler *compiler, Token start, Ops op) {
219 size_t n = 0;
220 while (has_next_token(compiler)) {
221 Token tok = peek_token(compiler);
222 if (tok.type == TOKEN_EOF) {
223 error_push((Error){
224 .type = ERR_TYPE_COMPILER,
225 .value = ERR_UNBALANCED_PAREN,
226 .line = start.line,
227 .col = start.column,
228 });
229 return;
230 }
231 if (tok.type == TOKEN_RPAREN) {
232 next_token(compiler);
233 if (n == 0) {
234 error_push((Error){
235 .type = ERR_TYPE_COMPILER,
236 .value = ERR_NOT_ENOUGH_ARGS,
237 .line = start.line,
238 .col = start.column,
239 });
240 }
241 return;
242 }
243 parse_tree(chunk, compiler);
244 add_code(chunk, op, start.line, start.column);
245 n++;
246 if (n > 1) {
247 error_push((Error){
248 .type = ERR_TYPE_COMPILER,
249 .value = ERR_TOO_MANY_ARGS,
250 .line = start.line,
251 .col = start.column,
252 });
253 }
254 }
255 error_push((Error){
256 .type = ERR_TYPE_COMPILER,
257 .value = ERR_UNBALANCED_PAREN,
258 .line = start.line,
259 .col = start.column,
260 });
261}
262
263void
264compile_list_simple_op(Chunk *chunk, Compiler *compiler, Token start, Ops op) {
265 if (has_next_token(compiler)) {
266 Token tok = peek_token(compiler);
267 if (tok.type == TOKEN_EOF) {
268 error_push((Error){
269 .type = ERR_TYPE_COMPILER,
270 .value = ERR_UNBALANCED_PAREN,
271 .line = start.line,
272 .col = start.column,
273 });
274 return;
275 }
276 if (tok.type != TOKEN_RPAREN) {
277 error_push((Error){
278 .type = ERR_TYPE_COMPILER,
279 .value = ERR_TOO_MANY_ARGS,
280 .line = start.line,
281 .col = start.column,
282 });
283 return;
284 }
285 next_token(compiler);
286 add_code(chunk, op, start.line, start.column);
287 return;
288 }
289 error_push((Error){
290 .type = ERR_TYPE_COMPILER,
291 .value = ERR_UNBALANCED_PAREN,
292 .line = start.line,
293 .col = start.column,
294 });
295}
296
297#define STR_ARRAY(ARR) (StringView){(ARR), array_size(ARR)}
298
299void
300compile_declare_op(Chunk *chunk, Compiler *compiler, Token start, Ops op) {
301 Token name = next_token(compiler);
302 if (name.type != TOKEN_SYMBOL) {
303 error_push((Error){
304 .type = ERR_TYPE_COMPILER,
305 .value = ERR_WRONG_ARG_TYPE,
306 .line = start.line,
307 .col = start.column,
308 });
309 return;
310 }
311
312 if (compiler->scope_depth <= 1) {
313 Object obj = make_symbol(name.value);
314 emit_constant(chunk, name, obj);
315 } else {
316 if (op == OP_DEF) {
317 op = OP_DEF_LOCAL;
318 // Check if the local is already registered.
319 Scope *scope = get_current_scope(compiler);
320 ssize_t idx = find_local_index(scope, name);
321 if (idx < 0) {
322 array_push(scope->locals, name.value);
323 idx = chunk->n_locals++;
324 }
325 emit_constant(chunk, name, FIXNUM_VAL(idx));
326 } else if (op == OP_SET) {
327 // FIXME: This is fucking ugly.
328 Scope *current_scope = get_current_scope(compiler);
329 ssize_t idx = -1;
330 // Check if the variable was already captured.
331 idx = find_captued_index(current_scope, name);
332 if (idx >= 0) {
333 emit_constant(chunk, name, FIXNUM_VAL(idx));
334 op = OP_SET_CAPTURED;
335 } else {
336 idx = find_local_index(current_scope, name);
337 if (idx >= 0) {
338 emit_constant(chunk, name, FIXNUM_VAL(idx));
339 op = OP_SET_LOCAL;
340 } else {
341 size_t depth = compiler->scope_depth - 2;
342 while (depth > 0) {
343 Scope *scope = &compiler->scopes[depth];
344 idx = find_local_index(scope, name);
345 if (idx >= 0) {
346 op = OP_SET_CAPTURED;
347 ssize_t captured_idx = array_size(current_scope->captured);
348 emit_constant(chunk, name, FIXNUM_VAL(captured_idx));
349 array_push(current_scope->captured, name);
350 break;
351 }
352 depth--;
353 }
354 if (idx < 0) {
355 Object obj = make_symbol(name.value);
356 emit_constant(chunk, name, obj);
357 }
358 }
359 }
360 }
361 }
362 // NOTE: We can have compiler support for preemptively finding if globals
363 // exist or not.
364
365 Token tok = peek_token(compiler);
366 if (name.type == TOKEN_EOF || tok.type == TOKEN_EOF) {
367 error_push((Error){
368 .type = ERR_TYPE_COMPILER,
369 .value = ERR_UNBALANCED_PAREN,
370 .line = start.line,
371 .col = start.column,
372 });
373 return;
374 }
375 if (name.type == TOKEN_RPAREN || tok.type == TOKEN_RPAREN) {
376 error_push((Error){
377 .type = ERR_TYPE_COMPILER,
378 .value = ERR_NOT_ENOUGH_ARGS,
379 .line = start.line,
380 .col = start.column,
381 });
382 return;
383 }
384 parse_tree(chunk, compiler);
385 if (peek_token(compiler).type != TOKEN_RPAREN) {
386 error_push((Error){
387 .type = ERR_TYPE_COMPILER,
388 .value = ERR_TOO_MANY_ARGS,
389 .line = start.line,
390 .col = start.column,
391 });
392 return;
393 }
394 next_token(compiler);
395 add_code(chunk, op, start.line, start.column);
396}
397
398void
399compile_lambda(Chunk *chunk, Compiler *compiler, Token start, StringView name) {
400 enter_scope(compiler);
401 Chunk *proc_chunk = chunk_init(name);
402 Object fun = make_lambda(proc_chunk);
403
404 // Prepeare parameters.
405 Token tok = next_token(compiler);
406 if (tok.type == TOKEN_LPAREN){
407 while (has_next_token(compiler)) {
408 Token tok = next_token(compiler);
409 if (tok.type == TOKEN_EOF) {
410 error_push((Error){
411 .type = ERR_TYPE_COMPILER,
412 .value = ERR_UNBALANCED_PAREN,
413 .line = start.line,
414 .col = start.column,
415 });
416 return;
417 }
418 if (tok.type == TOKEN_RPAREN) {
419 break;
420 }
421 if (tok.type != TOKEN_SYMBOL) {
422 error_push((Error){
423 .type = ERR_TYPE_COMPILER,
424 .value = ERR_WRONG_ARG_TYPE,
425 .line = tok.line,
426 .col = tok.column,
427 });
428 return;
429 }
430 // Check if parameters name already exists.
431 Scope *scope = get_current_scope(compiler);
432 ssize_t idx = find_local_index(scope, tok);
433 if (idx >= 0) {
434 error_push((Error){
435 .type = ERR_TYPE_COMPILER,
436 .value = ERR_AMBIGUOUS_PARAMS,
437 .line = tok.line,
438 .col = tok.column,
439 });
440 return;
441 }
442 array_push(scope->params, tok.value);
443 array_push(scope->locals, tok.value);
444 fun.closure->chunk->n_params++;
445 fun.closure->chunk->n_locals++;
446 }
447 } else if (tok.type != TOKEN_NIL) {
448 error_push((Error){
449 .type = ERR_TYPE_COMPILER,
450 .value = ERR_WRONG_ARG_TYPE,
451 .line = tok.line,
452 .col = tok.column,
453 });
454 return;
455 }
456
457 // Compile body.
458 while (has_next_token(compiler)) {
459 Token tok = peek_token(compiler);
460 if (tok.type == TOKEN_EOF) {
461 error_push((Error){
462 .type = ERR_TYPE_COMPILER,
463 .value = ERR_UNBALANCED_PAREN,
464 .line = start.line,
465 .col = start.column,
466 });
467 return;
468 }
469 if (tok.type == TOKEN_RPAREN) {
470 next_token(compiler);
471 break;
472 }
473 parse_tree(fun.closure->chunk, compiler);
474 }
475 add_code(fun.closure->chunk, OP_RETURN, start.line, start.column);
476
477 // Prepare closure value capture.
478 Scope *scope = get_current_scope(compiler);
479 size_t n_captured = array_size(scope->captured);
480 if (n_captured > 0) {
481 compiler->scope_depth--;
482 for (size_t i = 0; i < n_captured; i++) {
483 Token tok = scope->captured[i];
484 parse_symbol(chunk, compiler, tok);
485 }
486 // Number of captured values.
487 emit_constant(chunk, tok, FIXNUM_VAL(n_captured));
488
489 // Push created lambda to stack.
490 emit_constant(chunk, start, fun);
491
492 // Emit capture local instruction.
493 add_code(chunk, OP_CAPTURE_LOCAL, tok.line, tok.column);
494 compiler->scope_depth++;
495 } else {
496 emit_constant(chunk, start, fun);
497 }
498 exit_scope(compiler);
499}
500
501void
502compile_fun_op(Chunk *chunk, Compiler *compiler, Token start) {
503 Token name = peek_token(compiler);
504 if (name.type != TOKEN_SYMBOL) {
505 error_push((Error){
506 .type = ERR_TYPE_COMPILER,
507 .value = ERR_WRONG_ARG_TYPE,
508 .line = start.line,
509 .col = start.column,
510 });
511 return;
512 }
513 Object obj = make_symbol(name.value);
514 emit_constant(chunk, name, obj);
515 next_token(compiler);
516
517 compile_lambda(chunk, compiler, start, name.value);
518 add_code(chunk, OP_DEF, start.line, start.column);
519}
520
521void
522compile_call_op(Chunk *chunk, Compiler *compiler, Token start, Token name) {
523 if (name.type == TOKEN_SYMBOL) {
524 parse_symbol(chunk, compiler, name);
525 }
526
527 // Compile body.
528 size_t n = 0;
529 while (has_next_token(compiler)) {
530 Token tok = peek_token(compiler);
531 if (tok.type == TOKEN_EOF) {
532 error_push((Error){
533 .type = ERR_TYPE_COMPILER,
534 .value = ERR_UNBALANCED_PAREN,
535 .line = start.line,
536 .col = start.column,
537 });
538 return;
539 }
540 if (tok.type == TOKEN_RPAREN) {
541 next_token(compiler);
542 break;
543 }
544 parse_tree(chunk, compiler);
545 n++;
546 }
547 emit_constant(chunk, start, FIXNUM_VAL(n));
548 add_code(chunk, OP_CALL, start.line, start.column);
549}
550
551void
552compile_if_op(Chunk *chunk, Compiler *compiler, Token start) {
553 Token tok = peek_token(compiler);
554 if (tok.type == TOKEN_EOF) {
555 error_push((Error){
556 .type = ERR_TYPE_COMPILER,
557 .value = ERR_UNBALANCED_PAREN,
558 .line = start.line,
559 .col = start.column,
560 });
561 return;
562 }
563 if (tok.type == TOKEN_RPAREN) {
564 error_push((Error){
565 .type = ERR_TYPE_COMPILER,
566 .value = ERR_NOT_ENOUGH_ARGS,
567 .line = start.line,
568 .col = start.column,
569 });
570 return;
571 }
572
573 // Condition.
574 parse_tree(chunk, compiler);
575 size_t jmp_false = emit_jump(chunk, start, OP_JUMP_IF_FALSE, 0xFFFF);
576
577 // True expression.
578 parse_tree(chunk, compiler);
579
580 // No second expression.
581 if (peek_token(compiler).type == TOKEN_RPAREN) {
582 patch_jump(chunk, jmp_false);
583 next_token(compiler);
584 return;
585 }
586
587 // False expression.
588 size_t jmp_end = emit_jump(chunk, start, OP_JUMP, 0xFFFF);
589 patch_jump(chunk, jmp_false);
590 parse_tree(chunk, compiler);
591 patch_jump(chunk, jmp_end);
592
593 if (peek_token(compiler).type != TOKEN_RPAREN) {
594 error_push((Error){
595 .type = ERR_TYPE_COMPILER,
596 .value = ERR_TOO_MANY_ARGS,
597 .line = start.line,
598 .col = start.column,
599 });
600 return;
601 }
602 next_token(compiler);
603}
604
605void
606parse_list(Chunk *chunk, Compiler *compiler, Token start) {
607 if (!has_next_token(compiler)) {
608 error_push((Error){
609 .type = ERR_TYPE_COMPILER,
610 .value = ERR_UNBALANCED_PAREN,
611 .line = start.line,
612 .col = start.column,
613 });
614 return;
615 }
616 while (has_next_token(compiler)) {
617 Token tok = next_token(compiler);
618 if (tok.type == TOKEN_LPAREN) {
619 parse_list(chunk, compiler, tok);
620 }
621 switch (tok.type) {
622 case TOKEN_ADD: { compile_list_binary_op(chunk, compiler, start, OP_SUM); } break;
623 case TOKEN_SUB: { compile_list_binary_op(chunk, compiler, start, OP_SUB); } break;
624 case TOKEN_MUL: { compile_list_binary_op(chunk, compiler, start, OP_MUL); } break;
625 case TOKEN_DIV: { compile_list_binary_op(chunk, compiler, start, OP_DIV); } break;
626 case TOKEN_MOD: { compile_list_binary_op(chunk, compiler, start, OP_MOD); } break;
627 case TOKEN_NOT: { compile_list_unary_op(chunk, compiler, start, OP_NOT); } break;
628 case TOKEN_AND: { compile_list_binary_op(chunk, compiler, start, OP_AND); } break;
629 case TOKEN_OR: { compile_list_binary_op(chunk, compiler, start, OP_OR); } break;
630 case TOKEN_EQUAL: { compile_list_binary_op(chunk, compiler, start, OP_EQUAL); } break;
631 case TOKEN_LESS: { compile_list_binary_op(chunk, compiler, start, OP_LESS); } break;
632 case TOKEN_GREATER: { compile_list_binary_op(chunk, compiler, start, OP_GREATER); } break;
633 case TOKEN_LESS_EQUAL: { compile_list_binary_op(chunk, compiler, start, OP_LESS_EQUAL); } break;
634 case TOKEN_GREATER_EQUAL: { compile_list_binary_op(chunk, compiler, start, OP_GREATER_EQUAL); } break;
635 case TOKEN_PRINT: { compile_list_unary_op(chunk, compiler, start, OP_PRINT); } break;
636 case TOKEN_DISPLAY: { compile_list_unary_op(chunk, compiler, start, OP_DISPLAY); } break;
637 case TOKEN_NEWLINE: {
638 compile_list_simple_op(chunk, compiler, start, OP_NEWLINE);
639 emit_constant(chunk, start, NIL_VAL);
640 } break;
641 case TOKEN_DEF: { compile_declare_op(chunk, compiler, start, OP_DEF); } break;
642 case TOKEN_SET: { compile_declare_op(chunk, compiler, start, OP_SET); } break;
643 case TOKEN_FUN: { compile_fun_op(chunk, compiler, start); } break;
644 case TOKEN_LAMBDA: { compile_lambda(chunk, compiler, start, STRING("lambda")); } break;
645 case TOKEN_IF: { compile_if_op(chunk, compiler, start); } break;
646 default: {
647 compile_call_op(chunk, compiler, start, tok);
648 } break;
649 }
650 return;
651 }
652}
653
654void
655parse_tree(Chunk *chunk, Compiler *compiler) {
656 Token tok = next_token(compiler);
657 if (errors_n != 0) {
658 return;
659 }
660 switch (tok.type) {
661 case TOKEN_FIXNUM: {
662 parse_fixnum(chunk, tok);
663 return ;
664 } break;
665 case TOKEN_TRUE: {
666 emit_constant(chunk, tok, TRUE_VAL);
667 return;
668 } break;
669 case TOKEN_FALSE: {
670 emit_constant(chunk, tok, FALSE_VAL);
671 return;
672 } break;
673 case TOKEN_RPAREN: {
674 error_push((Error){
675 .type = ERR_TYPE_COMPILER,
676 .value = ERR_UNBALANCED_PAREN,
677 .line = tok.line,
678 .col = tok.column,
679 });
680 return;
681 } break;
682 case TOKEN_QUOTE: {
683 // Object *base = make_pair(obj_quote, obj_nil);
684 // base->cdr = make_pair(obj_nil, obj_nil);
685 // push_root(base);
686 // Object *next_obj = parse_tree(compiler);
687 // if (next_obj == obj_err) {
688 // return obj_err;
689 // }
690 // base->cdr->car = next_obj;
691 // return base;
692 return;
693 } break;
694 case TOKEN_LPAREN: {
695 parse_list(chunk, compiler, tok);
696 return;
697 } break;
698 case TOKEN_STRING: {
699 Object obj = make_string(tok.value);
700 emit_constant(chunk, tok, obj);
701 return;
702 } break;
703 case TOKEN_SYMBOL: {
704 parse_symbol(chunk, compiler, tok);
705 return;
706 } break;
707 case TOKEN_NIL: {
708 emit_constant(chunk, tok, NIL_VAL);
709 return;
710 } break;
711 default: {
712 break;
713 } break;
714 }
715 error_push((Error){
716 .type = ERR_TYPE_COMPILER,
717 .value = ERR_EOF_REACHED,
718 .line = tok.line,
719 .col = tok.column,
720 });
721 return;
722}
723
724Chunk *
725compile(Token *tokens) {
726 Chunk *chunk = NULL;
727 chunk = NEW_CHUNK("main");
728 Compiler compiler = (Compiler){
729 .tokens = tokens,
730 .current = 0,
731 .scope_depth = 0,
732 };
733 enter_scope(&compiler);
734 Token main_start = peek_token(&compiler);
735 while (has_next_token(&compiler)) {
736 Token start = peek_token(&compiler);
737 parse_tree(chunk, &compiler);
738 if (peek_token(&compiler).type == TOKEN_EOF) {
739 break;
740 }
741 add_code(chunk, OP_DROP, start.line, start.column);
742 }
743 add_code(chunk, OP_RETURN, main_start.line, main_start.column);
744 exit_scope(&compiler);
745 return chunk;
746}
747
748#endif // BDL_COMPILER_H
diff --git a/src/bytecode/darray.h b/src/bytecode/darray.h
deleted file mode 100755
index fa4e293..0000000
--- a/src/bytecode/darray.h
+++ /dev/null
@@ -1,81 +0,0 @@
1#ifndef BDL_DARRAY_H
2#define BDL_DARRAY_H
3
4#include <string.h>
5
6typedef struct ArrayHeader {
7 size_t size;
8 size_t cap;
9} ArrayHeader;
10
11// Header/Size/capacity accessors.
12#define array_head(ARR) ((ArrayHeader *)((char *)(ARR) - sizeof(ArrayHeader)))
13#define array_size(ARR) ((ARR) ? array_head(ARR)->size : 0)
14#define array_cap(ARR) ((ARR) ? array_head(ARR)->cap : 0)
15
16// Initialize a dynamic array ARR with N elements. The initialization doesn't
17// zero out the data, so thread carefully..
18#define array_init(ARR,N) ((ARR) = _array_reserve(N, sizeof(*(ARR))))
19
20// Push a given element T to the dynamic array ARR.
21#define array_push(ARR, T) \
22 ((ARR) = _array_maybe_grow(ARR, sizeof(T)), \
23 (ARR)[array_head(ARR)->size++] = (T))
24
25// Return the last element of the array. Can be used to build stacks.
26#define array_pop(ARR) (ARR)[--array_head(ARR)->size]
27
28// Return the value stored at the OFFSET position from the tail of the array.
29#define array_peek(ARR, OFFSET) (ARR)[array_head(ARR)->size - 1 - (OFFSET)]
30
31// Insert N bytes from the SRC array into the ARR dynamic array.
32#define array_insert(ARR, SRC, N) \
33 ((ARR) = _array_insert(ARR, SRC, N, sizeof(*(ARR))))
34
35// Free the memory from the original allocated position.
36#define array_free(ARR) ((ARR) ? free(array_head(ARR)), (ARR) = NULL : 0)
37
38static inline void *
39_array_reserve(size_t num_elem, size_t type_size) {
40 char *p = malloc(num_elem * type_size + sizeof(ArrayHeader));
41 p += sizeof(ArrayHeader);
42 array_head(p)->size = 0;
43 array_head(p)->cap = num_elem;
44 return p;
45}
46
47static inline void *
48_array_maybe_grow(void *arr, size_t type_size) {
49 ArrayHeader *head = array_head(arr);
50 if (head->cap == head->size) {
51 if (head->cap == 0) {
52 head->cap++;
53 } else {
54 head->cap *= 2;
55 }
56 head = realloc(head, head->cap * type_size + sizeof(ArrayHeader));
57 }
58 arr = (char *)head + sizeof(ArrayHeader);
59 return arr;
60}
61
62static inline
63char * _array_insert(char *arr, const char *src, size_t n_bytes, size_t type_size) {
64 ArrayHeader *head = array_head(arr);
65 size_t new_size = n_bytes + head->size;
66 if (new_size > head->cap * type_size) {
67 if (head->cap == 0) {
68 head->cap = 1;
69 }
70 while (new_size >= head->cap * type_size) {
71 head->cap *= 2;
72 }
73 head = realloc(head, head->cap * type_size + sizeof(ArrayHeader));
74 }
75 arr = (char *)head + sizeof(ArrayHeader);
76 memcpy((arr + head->size), src, n_bytes);
77 head->size = new_size;
78 return arr;
79}
80
81#endif // BDL_DARRAY_H
diff --git a/src/bytecode/debug.h b/src/bytecode/debug.h
deleted file mode 100755
index b21d8e6..0000000
--- a/src/bytecode/debug.h
+++ /dev/null
@@ -1,105 +0,0 @@
1#ifndef BDL_DEBUG_H
2#define BDL_DEBUG_H
3
4#include "chunk.h"
5#include "objects.h"
6
7void disassemble_chunk(Chunk *chunk);
8size_t disassemble_instruction(Chunk *chunk, size_t offset);
9
10static const char* ops_str[] = {
11 // Load/store ops.
12 [OP_CONSTANT] = "OP_CONSTANT",
13 [OP_LOCAL] = "OP_LOCAL",
14 [OP_CAPTURED] = "OP_CAPTURED",
15 [OP_CAPTURE_LOCAL] = "OP_CAPTURE_LOCAL",
16 [OP_SET_CAPTURED] = "OP_SET_CAPTURED",
17 [OP_DEF_LOCAL] = "OP_DEF_LOCAL",
18 [OP_SET_LOCAL] = "OP_SET_LOCAL",
19 [OP_DEF] = "OP_DEF",
20 [OP_SET] = "OP_SET",
21 [OP_GET] = "OP_GET",
22 // Arithmetic ops.
23 [OP_SUM] = "OP_SUM",
24 [OP_SUB] = "OP_SUB",
25 [OP_MUL] = "OP_MUL",
26 [OP_DIV] = "OP_DIV",
27 [OP_MOD] = "OP_MOD",
28 // Logic ops.
29 [OP_NOT] = "OP_NOT",
30 [OP_AND] = "OP_AND",
31 [OP_OR] = "OP_OR",
32 // Numerical comparison ops.
33 [OP_EQUAL] = "OP_EQUAL",
34 [OP_LESS] = "OP_LESS",
35 [OP_GREATER] = "OP_GREATER",
36 [OP_LESS_EQUAL] = "OP_LESS_EQUAL",
37 [OP_GREATER_EQUAL] = "OP_GREATER_EQUAL",
38 // Jump/conditional ops.
39 [OP_JUMP] = "OP_JUMP",
40 [OP_JUMP_IF_FALSE] = "OP_JUMP_IF_FALSE",
41 // Display ops.
42 [OP_DISPLAY] = "OP_DISPLAY",
43 [OP_PRINT] = "OP_PRINT",
44 [OP_NEWLINE] = "OP_NEWLINE",
45 // Procedures.
46 [OP_CALL] = "OP_CALL",
47 [OP_RETURN] = "OP_RETURN",
48 // Clear stack after each statement.
49 [OP_DROP] = "OP_DROP",
50};
51
52void
53disassemble_chunk(Chunk *chunk) {
54 printf("===== %.*s =====\n", (int)array_size(chunk->name), chunk->name);
55 printf("code:\n");
56 size_t offset = 0;
57 while (offset < array_size(chunk->code)) {
58 offset = disassemble_instruction(chunk, offset);
59 }
60 printf("\nconstants:\n");
61 offset = 0;
62 while (offset < array_size(chunk->constants)) {
63 printf("\t%03ld -> ", offset);
64 object_display(chunk->constants[offset]);
65 printf("\n");
66 offset++;
67 }
68 printf("\n");
69}
70
71size_t
72disassemble_instruction(Chunk *chunk, size_t offset) {
73 printf("\t%04ld ", offset);
74 if (offset > 0
75 && chunk->lines[offset].line == chunk->lines[offset - 1].line
76 && chunk->lines[offset].col == chunk->lines[offset - 1].col) {
77 printf("%4s|%-4s ", " ", " ");
78 } else {
79 printf("%4ld:%-4ld ", chunk->lines[offset].line, chunk->lines[offset].col);
80 }
81 u8 instruction = chunk->code[offset];
82 switch (instruction) {
83 case OP_CONSTANT: {
84 u8 constant = chunk->code[offset + 1];
85 printf("%-16s %4d -> ", ops_str[instruction], constant);
86 object_display(chunk->constants[constant]);
87 printf("\n");
88 return offset + 2;
89 } break;
90 case OP_JUMP:
91 case OP_JUMP_IF_FALSE: {
92 u16 a = chunk->code[offset + 1];
93 u16 b = chunk->code[offset + 2];
94 s16 jmp = (a << 8) | b;
95 printf("%-16s %4d\n", ops_str[instruction], jmp);
96 return offset + 3;
97 } break;
98 default: {
99 printf("%s\n", ops_str[instruction]);
100 return offset + 1;
101 } break;
102 }
103}
104
105#endif // BDL_DEBUG_H
diff --git a/src/bytecode/errors.c b/src/bytecode/errors.c
deleted file mode 100755
index b2aab93..0000000
--- a/src/bytecode/errors.c
+++ /dev/null
@@ -1,52 +0,0 @@
1#include "errors.h"
2
3static const char* error_msgs[] = {
4 [ERR_UNKNOWN] = "error: something unexpected happened",
5 [ERR_UNMATCHED_STRING] = "error: unmatched string delimiter",
6 [ERR_UNBALANCED_PAREN] = "error: unbalanced parentheses",
7 [ERR_NOT_IMPLEMENTED] = "error: not implemented",
8 [ERR_EOF_REACHED] = "error: EOF reached",
9 [ERR_UNKNOWN_TOKEN] = "error: unknown token",
10 [ERR_UNKNOWN_OBJ_TYPE] = "error: can't eval unknown object type",
11 [ERR_NOT_A_SYMBOL] = "error: object is not a symbol",
12 [ERR_SYMBOL_NOT_FOUND] = "error: symbol not found",
13 [ERR_OBJ_NOT_CALLABLE] = "error: object is not callable",
14 [ERR_NOT_ENOUGH_ARGS] = "error: not enough arguments",
15 [ERR_TOO_MANY_ARGS] = "error: too many arguments",
16 [ERR_WRONG_ARG_TYPE] = "error: wrong argument type",
17 [ERR_DIVISION_BY_ZERO] = "error: division by zero",
18 [ERR_PC_OOB] = "error: pc out of bounds",
19 [ERR_EMPTY_CHUNK] = "error: empty chunk",
20 [ERR_AMBIGUOUS_PARAMS] = "error: ambiguous parameter names",
21};
22
23static Error errors[ERR_MAX_NUMBER];
24static size_t errors_n = 0;
25static bool supress_errors = false;
26
27void
28error_push(Error error) {
29 if (errors_n < ERR_MAX_NUMBER) {
30 errors[errors_n++] = error;
31 }
32}
33
34void
35report_errors(char *file_name) {
36 for (size_t i = 0; i < errors_n; i++) {
37 Error err = errors[i];
38 fprintf(stderr, "%s", file_name);
39 if (err.line != 0) {
40 fprintf(stderr, ":%ld:%ld", err.line, err.col);
41 }
42 switch (err.type) {
43 case ERR_TYPE_LEXER: { fprintf(stderr, ": [lexer]"); } break;
44 case ERR_TYPE_COMPILER: { fprintf(stderr, ": [compiler]"); } break;
45 case ERR_TYPE_RUNTIME: { fprintf(stderr, ": [runtime]"); } break;
46 case ERR_TYPE_PARSER: { fprintf(stderr, ": [parser]"); } break;
47 default: break;
48 }
49 fprintf(stderr, " %s\n", error_msgs[err.value]);
50 }
51 errors_n = 0;
52}
diff --git a/src/bytecode/errors.h b/src/bytecode/errors.h
deleted file mode 100755
index 8f4386e..0000000
--- a/src/bytecode/errors.h
+++ /dev/null
@@ -1,46 +0,0 @@
1#ifndef BDL_ERRORS_H
2#define BDL_ERRORS_H
3
4typedef enum ErrorType {
5 ERR_TYPE_OK,
6 ERR_TYPE_LEXER,
7 ERR_TYPE_PARSER,
8 ERR_TYPE_COMPILER,
9 ERR_TYPE_RUNTIME,
10} ErrorType;
11
12typedef enum ErrorValue {
13 ERR_UNKNOWN = 0,
14 ERR_UNMATCHED_STRING,
15 ERR_UNBALANCED_PAREN,
16 ERR_NOT_IMPLEMENTED,
17 ERR_EOF_REACHED,
18 ERR_UNKNOWN_TOKEN,
19 ERR_UNKNOWN_OBJ_TYPE,
20 ERR_NOT_A_SYMBOL,
21 ERR_SYMBOL_NOT_FOUND,
22 ERR_OBJ_NOT_CALLABLE,
23 ERR_NOT_ENOUGH_ARGS,
24 ERR_TOO_MANY_ARGS,
25 ERR_WRONG_ARG_TYPE,
26 ERR_DIVISION_BY_ZERO,
27 ERR_AMBIGUOUS_PARAMS,
28
29 // Bytecode interpreter.
30 ERR_PC_OOB,
31 ERR_EMPTY_CHUNK,
32} ErrorValue;
33
34typedef struct Error {
35 ErrorType type;
36 ErrorValue value;
37 size_t line;
38 size_t col;
39} Error;
40
41void error_push(Error error);
42void report_errors(char *file_name);
43
44#define ERR_MAX_NUMBER 16
45
46#endif // BDL_ERRORS_H
diff --git a/src/bytecode/hashtable.h b/src/bytecode/hashtable.h
deleted file mode 100644
index 7c0c380..0000000
--- a/src/bytecode/hashtable.h
+++ /dev/null
@@ -1,208 +0,0 @@
1#ifndef BDL_HASHTABLE_H
2#define BDL_HASHTABLE_H
3
4#include "darray.h"
5#include "objects.h"
6
7// Minimum table capacity.
8#define HT_MIN_CAP 4
9#define HT_MIN_SHIFT 2
10
11// Adjust the load factor threshold at which the table will grow on insertion.
12#define HT_LOAD_THRESHOLD 0.8
13
14typedef struct HashTablePair {
15 Object *key;
16 Object *value;
17} HashTablePair;
18
19struct HashTable;
20typedef uint64_t (HashFunction)(const struct HashTable *table, void *bytes);
21
22typedef struct HashTable {
23 // All available key-value pairs as a dynamic array.
24 HashTablePair *pairs;
25
26 // Internal storage.
27 Object *keys;
28 Object *values;
29
30 // Hash function.
31 HashFunction *hash_func;
32
33 // This table expects the number of buckets to grow in powers of two. To
34 // speedup the default hashing, we memoize the number of bits equivalent to
35 // that power of 2:
36 //
37 // cap := 1024 = 2 ^ 10, shift_amount := 10
38 //
39 uint8_t shift_amount;
40} HashTable;
41
42// Hash a byte stream using a circular shift + XOR hash function.
43static inline uint64_t
44_xor_shift_hash(const char *key, size_t n) {
45 uint64_t hash = 0x65d9d65f6a19574f;
46 char *last = (char *)key + n;
47 while (key != last) {
48 hash ^= (uint64_t)*key++;
49 hash = (hash << 8) | (hash >> (64 - 8));
50 }
51 return hash;
52}
53
54// Use Fibonacci hashing to map a hash to a value in range of the table.
55static inline uint64_t
56_fibonacci_hash(uint64_t hash, size_t shift_amount) {
57 return (hash * UINT64_C(11400714819323198485)) >> (64 - shift_amount);
58}
59
60uint64_t
61_symbol_hash(const HashTable *table, void *key) {
62 Object *obj = key;
63 uint64_t hash = _xor_shift_hash(obj->text, array_size(obj->text));
64 hash = _fibonacci_hash(hash, table->shift_amount);
65 return hash;
66}
67
68static inline float
69ht_load_factor(const HashTable *table) {
70 return (float)array_size(table->pairs) / (float)array_cap(table->pairs);
71}
72
73HashTable *
74ht_init(void) {
75 HashTable *table = malloc(sizeof(HashTable));
76 *table = (HashTable){0};
77 array_init(table->pairs, HT_MIN_CAP);
78 array_init(table->keys, HT_MIN_CAP);
79 array_init(table->values, HT_MIN_CAP);
80 for (size_t i = 0; i < array_cap(table->pairs); i++) {
81 table->pairs[i] = (HashTablePair){NULL, NULL};
82 }
83 table->shift_amount = HT_MIN_SHIFT;
84 table->hash_func = _symbol_hash;
85 return table;
86}
87
88void
89_ht_insert(HashTable *table, Object key, Object value) {
90 size_t position = table->hash_func(table, &key);
91 size_t probe_position = position;
92
93 // Verify the key in that position is free. If not, use linear probing to
94 // find the next free slot.
95 HashTablePair *pairs = table->pairs;
96 bool update = false;
97 while (true) {
98 if (pairs[probe_position].key == NULL) {
99 array_head(pairs)->size++;
100 break;
101 }
102 if (object_equal(*pairs[probe_position].key, key)) {
103 update = true;
104 break;
105 }
106 if (probe_position == array_cap(pairs) - 1) {
107 probe_position = 0;
108 } else {
109 probe_position++;
110 }
111 }
112
113 if (!update) {
114 array_push(table->keys, object_copy(key));
115 array_push(table->values, value);
116 pairs[probe_position].key = &table->keys[array_size(table->keys) - 1];
117 pairs[probe_position].value = &table->values[array_size(table->values) - 1];
118 } else {
119 *pairs[probe_position].value = value;
120 }
121}
122
123void
124_ht_maybe_grow(HashTable *table) {
125 if (ht_load_factor(table) < HT_LOAD_THRESHOLD) {
126 return;
127 }
128
129 // Create a new array with 2x capacity.
130 HashTablePair *old_pairs = table->pairs;
131 Object *old_keys = table->keys;
132 Object *old_values = table->values;
133 table->pairs = NULL;
134 table->keys = NULL;
135 table->values = NULL;
136 array_init(table->pairs, array_cap(old_pairs) * 2);
137 array_init(table->keys, array_cap(old_pairs) * 2);
138 array_init(table->values, array_cap(old_pairs) * 2);
139 for (size_t i = 0; i < array_cap(table->pairs); i++) {
140 table->pairs[i] = (HashTablePair){NULL, NULL};
141 }
142 table->shift_amount++;
143
144 // Hash everything in the table for the new array capacity.
145 for (size_t i = 0; i < array_cap(old_pairs); i++) {
146 if (old_pairs[i].key != NULL) {
147 _ht_insert(table, *old_pairs[i].key, *old_pairs[i].value);
148 }
149 }
150
151 // Free old arrays.
152 array_free(old_pairs);
153 for (size_t i = 0; i < array_size(old_keys); i++) {
154 object_free(&old_keys[i]);
155 }
156 array_free(old_keys);
157 array_free(old_values);
158}
159
160void
161ht_insert(HashTable *table, Object key, Object value) {
162 _ht_maybe_grow(table);
163 _ht_insert(table, key, value);
164 return;
165}
166
167Object *
168ht_lookup(const HashTable *table, Object key) {
169 size_t position = table->hash_func(table, &key);
170 size_t probe_position = position;
171
172 // Verify the key in that position is the same. If not perform linear
173 // probing to find it.
174 HashTablePair *pairs = table->pairs;
175 while (true) {
176 if (pairs[probe_position].key == NULL) {
177 return NULL;
178 }
179 if (object_equal(*pairs[probe_position].key, key)) {
180 break;
181 }
182 if (probe_position == array_cap(pairs) - 1) {
183 probe_position = 0;
184 } else {
185 probe_position++;
186 }
187 if (probe_position == position) {
188 return NULL;
189 }
190 }
191 return pairs[probe_position].value;
192}
193
194void
195ht_free(HashTable *table) {
196 if (table == NULL) {
197 return;
198 }
199 array_free(table->pairs);
200 for (size_t i = 0; i < array_size(table->keys); i++) {
201 object_free(&table->keys[i]);
202 }
203 array_free(table->keys);
204 array_free(table->values);
205 free(table);
206}
207
208#endif // BDL_HASHTABLE_H
diff --git a/src/bytecode/lexer.c b/src/bytecode/lexer.c
deleted file mode 100755
index a80c845..0000000
--- a/src/bytecode/lexer.c
+++ /dev/null
@@ -1,294 +0,0 @@
1#include "lexer.h"
2
3static const char* token_str[] = {
4 [TOKEN_UNKNOWN] = "TOKEN_UNKNOWN",
5 [TOKEN_LPAREN] = "TOKEN_LPAREN",
6 [TOKEN_RPAREN] = "TOKEN_RPAREN",
7 [TOKEN_FIXNUM] = "TOKEN_FIXNUM",
8 [TOKEN_SYMBOL] = "TOKEN_SYMBOL",
9 [TOKEN_STRING] = "TOKEN_STRING",
10 [TOKEN_NIL] = "TOKEN_NIL",
11 [TOKEN_QUOTE] = "TOKEN_QUOTE",
12 [TOKEN_TRUE] = "TOKEN_TRUE",
13 [TOKEN_FALSE] = "TOKEN_FALSE",
14 [TOKEN_IF] = "TOKEN_IF",
15 [TOKEN_ELSE] = "TOKEN_ELSE",
16 [TOKEN_DEF] = "TOKEN_DEF",
17 [TOKEN_SET] = "TOKEN_SET",
18 [TOKEN_FUN] = "TOKEN_FUN",
19 [TOKEN_LAMBDA] = "TOKEN_LAMBDA",
20 [TOKEN_DISPLAY] = "TOKEN_DISPLAY",
21 [TOKEN_PRINT] = "TOKEN_PRINT",
22 [TOKEN_NEWLINE] = "TOKEN_NEWLINE",
23 [TOKEN_ADD] = "TOKEN_ADD",
24 [TOKEN_SUB] = "TOKEN_SUB",
25 [TOKEN_MUL] = "TOKEN_MUL",
26 [TOKEN_DIV] = "TOKEN_DIV",
27 [TOKEN_MOD] = "TOKEN_MOD",
28 [TOKEN_NOT] = "TOKEN_NOT",
29 [TOKEN_AND] = "TOKEN_AND",
30 [TOKEN_OR] = "TOKEN_OR",
31 [TOKEN_EQUAL] = "TOKEN_EQUAL",
32 [TOKEN_LESS] = "TOKEN_LESS",
33 [TOKEN_GREATER] = "TOKEN_GREATER",
34 [TOKEN_LESS_EQUAL] = "TOKEN_LESS_EQUAL",
35 [TOKEN_GREATER_EQUAL] = "TOKEN_GREATER_EQUAL",
36 [TOKEN_EOF] = "TOKEN_EOF",
37};
38
39void
40print_token(Token tok) {
41 printf("LINE: %3ld COL: %3ld ", tok.line, tok.column);
42 printf("%s", token_str[tok.type]);
43 switch (tok.type) {
44 case TOKEN_FIXNUM: {
45 printf(" -> ");
46 sv_write(&tok.value);
47 } break;
48 case TOKEN_SYMBOL: {
49 printf(" -> ");
50 sv_write(&tok.value);
51 } break;
52 case TOKEN_STRING: {
53 printf(" -> ");
54 sv_write(&tok.value);
55 } break;
56 default: {
57 } break;
58 }
59 printf("\n");
60}
61
62char
63scan_next(Scanner *scanner) {
64 char c = sv_next(&scanner->current);
65 if (c == '\n') {
66 scanner->line_number++;
67 scanner->col_number = 1;
68 } else {
69 scanner->col_number++;
70 }
71 scanner->offset++;
72 return c;
73}
74
75char
76scan_peek(const Scanner *scanner) {
77 return sv_peek(&scanner->current);
78}
79
80bool
81scan_has_next(const Scanner *scanner) {
82 return scanner->current.n != 0;
83}
84
85void
86skip_whitespace(Scanner *scanner) {
87 while (scan_has_next(scanner)) {
88 char c = scan_peek(scanner);
89 switch (c) {
90 case ' ':
91 case '\f':
92 case '\n':
93 case '\r':
94 case '\t':
95 case '\v': {
96 scan_next(scanner);
97 } break;
98 default: {
99 return;
100 } break;
101 }
102 }
103}
104
105bool
106is_delimiter(char c) {
107 switch (c) {
108 case EOF:
109 case '\0':
110 case ';':
111 case '"':
112 case '\'':
113 case '(':
114 case ')':
115 case ' ':
116 case '\f':
117 case '\n':
118 case '\r':
119 case '\t':
120 case '\v': {
121 return true;
122 } break;
123 }
124 return false;
125}
126
127#define TOKEN_IS_KEYWORD(VAL, KEYWORD) \
128 sv_equal(&(VAL), &(StringView){(KEYWORD), sizeof(KEYWORD) - 1})
129
130TokenType
131find_primitive_type(const StringView value) {
132 bool is_fixnum = true;
133 for (size_t i = 0; i < value.n; i++) {
134 char c = value.start[i];
135 if (i == 0 && c == '-' && value.n > 1) {
136 continue;
137 }
138 if (!(c >= '0' && c <= '9')) {
139 is_fixnum = false;
140 break;
141 }
142 }
143 if (is_fixnum) {
144 return TOKEN_FIXNUM;
145 }
146 if (TOKEN_IS_KEYWORD(value, "true")) { return TOKEN_TRUE; }
147 if (TOKEN_IS_KEYWORD(value, "false")) { return TOKEN_FALSE; }
148 if (TOKEN_IS_KEYWORD(value, "if")) { return TOKEN_IF; }
149 if (TOKEN_IS_KEYWORD(value, "else")) { return TOKEN_ELSE; }
150 if (TOKEN_IS_KEYWORD(value, "def")) { return TOKEN_DEF; }
151 if (TOKEN_IS_KEYWORD(value, "set!")) { return TOKEN_SET; }
152 if (TOKEN_IS_KEYWORD(value, "fun")) { return TOKEN_FUN; }
153 if (TOKEN_IS_KEYWORD(value, "lambda")) { return TOKEN_LAMBDA; }
154 if (TOKEN_IS_KEYWORD(value, "display")) { return TOKEN_DISPLAY; }
155 if (TOKEN_IS_KEYWORD(value, "print")) { return TOKEN_PRINT; }
156 if (TOKEN_IS_KEYWORD(value, "newline")) { return TOKEN_NEWLINE; }
157 if (TOKEN_IS_KEYWORD(value, "+")) { return TOKEN_ADD; }
158 if (TOKEN_IS_KEYWORD(value, "-")) { return TOKEN_SUB; }
159 if (TOKEN_IS_KEYWORD(value, "*")) { return TOKEN_MUL; }
160 if (TOKEN_IS_KEYWORD(value, "/")) { return TOKEN_DIV; }
161 if (TOKEN_IS_KEYWORD(value, "%")) { return TOKEN_MOD; }
162 if (TOKEN_IS_KEYWORD(value, "not")) { return TOKEN_NOT; }
163 if (TOKEN_IS_KEYWORD(value, "and")) { return TOKEN_AND; }
164 if (TOKEN_IS_KEYWORD(value, "or")) { return TOKEN_OR; }
165 if (TOKEN_IS_KEYWORD(value, "=")) { return TOKEN_EQUAL; }
166 if (TOKEN_IS_KEYWORD(value, "<")) { return TOKEN_LESS; }
167 if (TOKEN_IS_KEYWORD(value, ">")) { return TOKEN_GREATER; }
168 if (TOKEN_IS_KEYWORD(value, "<=")) { return TOKEN_LESS_EQUAL; }
169 if (TOKEN_IS_KEYWORD(value, ">=")) { return TOKEN_GREATER_EQUAL; }
170
171 return TOKEN_SYMBOL;
172}
173
174Token *
175tokenize(const StringView *sv) {
176 Token *tokens = NULL;
177 array_init(tokens, 1);
178 Scanner scanner = (Scanner){
179 .current = *sv,
180 .line_number = 1,
181 .col_number = 1,
182 };
183
184 while (scan_has_next(&scanner)) {
185 skip_whitespace(&scanner);
186 size_t line = scanner.line_number;
187 size_t col = scanner.col_number;
188 size_t offset = scanner.offset;
189 char c = scan_next(&scanner);
190 switch (c) {
191 case ';': {
192 while ((c = scan_next(&scanner)) != '\n' && c != '\0') {}
193 } break;
194 case '"': {
195 char prev = c;
196 bool found = false;
197 size_t n = 0;
198 while (scan_has_next(&scanner)) {
199 c = scan_next(&scanner);
200 if (c == '"' && prev != '\\') {
201 found = true;
202 break;
203 }
204 prev = c;
205 n++;
206 }
207 if (!found) {
208 error_push((Error){
209 .type = ERR_TYPE_LEXER,
210 .value = ERR_UNMATCHED_STRING,
211 .line = line,
212 .col = col,
213 });
214 return tokens;
215 }
216 Token token = (Token){
217 .value = (StringView){
218 .start = &sv->start[offset + 1],
219 .n = n,
220 },
221 .type = TOKEN_STRING,
222 .line = line,
223 .column = col,
224 };
225 array_push(tokens, token);
226 } break;
227 case '\'': {
228 Token token = (Token){
229 .type = TOKEN_QUOTE,
230 .line = line,
231 .column = col,
232 };
233 array_push(tokens, token);
234 } break;
235 case '(': {
236 if (scan_peek(&scanner) == ')') {
237 scan_next(&scanner);
238 Token token = (Token){
239 .type = TOKEN_NIL,
240 .line = line,
241 .column = col,
242 };
243 array_push(tokens, token);
244 } else {
245 Token token = (Token){
246 .type = TOKEN_LPAREN,
247 .line = line,
248 .column = col,
249 };
250 array_push(tokens, token);
251 }
252 } break;
253 case ')': {
254 Token token = (Token){
255 .type = TOKEN_RPAREN,
256 .line = line,
257 .column = col,
258 };
259 array_push(tokens, token);
260 } break;
261 default: {
262 size_t n = 1;
263 while (!is_delimiter(scan_peek(&scanner))) {
264 scan_next(&scanner);
265 n++;
266 }
267 if (c == EOF || c == '\0') {
268 break;
269 }
270 Token token = (Token){
271 .value = (StringView){
272 .start = &sv->start[offset],
273 .n = n,
274 },
275 .type = TOKEN_SYMBOL,
276 .line = line,
277 .column = col,
278 };
279 token.type = find_primitive_type(token.value);
280 array_push(tokens, token);
281 } break;
282 }
283 }
284
285 // Push EOF token.
286 Token token = (Token){
287 .type = TOKEN_EOF,
288 .line = scanner.line_number,
289 .column = 1,
290 };
291 array_push(tokens, token);
292
293 return tokens;
294}
diff --git a/src/bytecode/lexer.h b/src/bytecode/lexer.h
deleted file mode 100755
index 3cadf30..0000000
--- a/src/bytecode/lexer.h
+++ /dev/null
@@ -1,92 +0,0 @@
1#ifndef BDL_LEXER_H
2#define BDL_LEXER_H
3
4#include "string_view.h"
5
6typedef enum TokenType {
7 TOKEN_UNKNOWN = 0,
8
9 // Parentheses.
10 TOKEN_LPAREN,
11 TOKEN_RPAREN,
12
13 // Primitive types.
14 TOKEN_FIXNUM,
15 TOKEN_SYMBOL,
16 TOKEN_STRING,
17
18 // Keywords.
19 TOKEN_NIL,
20 TOKEN_QUOTE,
21 TOKEN_TRUE,
22 TOKEN_FALSE,
23 TOKEN_IF,
24 TOKEN_ELSE,
25 TOKEN_DEF,
26 TOKEN_SET,
27 TOKEN_FUN,
28 TOKEN_LAMBDA,
29 TOKEN_DISPLAY,
30 TOKEN_PRINT,
31 TOKEN_NEWLINE,
32
33 // Arithmetic.
34 TOKEN_ADD,
35 TOKEN_SUB,
36 TOKEN_MUL,
37 TOKEN_DIV,
38 TOKEN_MOD,
39
40 // Boolean comparisons.
41 TOKEN_NOT,
42 TOKEN_AND,
43 TOKEN_OR,
44 TOKEN_EQUAL,
45 TOKEN_LESS,
46 TOKEN_GREATER,
47 TOKEN_LESS_EQUAL,
48 TOKEN_GREATER_EQUAL,
49
50 TOKEN_EOF,
51} TokenType;
52
53typedef struct Token {
54 TokenType type;
55 StringView value;
56 size_t line;
57 size_t column;
58} Token;
59
60typedef struct Scanner {
61 StringView current;
62 size_t line_number;
63 size_t col_number;
64 size_t offset;
65} Scanner;
66
67// Print a token to standard output for debugging purposes.
68void print_token(Token tok);
69
70// Same functionality as the ScanView pairs, but keeping track of line and
71// column numbers.
72char scan_next(Scanner *scanner);
73char scan_peek(const Scanner *scanner);
74
75// Check if the current scanner still have characters left.
76bool scan_has_next(const Scanner *scanner);
77
78// Advance the scanner until we ran out of whitespace.
79void skip_whitespace(Scanner *scanner);
80
81// Check if a given character is a delimiter.
82bool is_delimiter(char c);
83
84// Extract the token type from the current string.
85TokenType find_primitive_type(const StringView value);
86
87// Generate a list of tokens from the given string.
88Token * tokenize(const StringView *sv);
89
90#define TOK_BUF_CAP 256
91
92#endif // BDL_LEXER_H
diff --git a/src/bytecode/main.c b/src/bytecode/main.c
deleted file mode 100755
index 4b80f71..0000000
--- a/src/bytecode/main.c
+++ /dev/null
@@ -1,214 +0,0 @@
1#include <assert.h>
2#include <getopt.h>
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6
7//
8// Config.
9//
10
11#ifdef DEBUG
12#define DEBUG_TRACE_EXECUTION
13#endif
14
15#include "vm.h"
16#include "errors.c"
17#include "chunk.c"
18#include "objects.c"
19#include "compiler.h"
20#include "ops.h"
21#include "debug.h"
22#include "lexer.c"
23#include "read_line.c"
24#include "string_view.c"
25
26static VM vm;
27
28void
29init(void) {
30 vm_init(&vm);
31}
32
33void
34halt(void) {
35 vm_free(&vm);
36}
37
38void
39process_source(const StringView *source) {
40 // Read tokens.
41 Token *tokens = tokenize(source);
42 if (errors_n != 0) {
43 array_free(tokens);
44 return;
45 }
46
47 // Compile chunk.
48 Chunk *main = compile(tokens);
49 if (errors_n != 0) {
50 chunk_free(main);
51 array_free(tokens);
52 return;
53 }
54
55#ifdef DEBUG
56 disassemble_chunk(main);
57#endif
58
59 // Interpret chunk.
60 Object main_proc = make_lambda(main);
61 CallFrame frame = (CallFrame){
62 .closure = main_proc.closure,
63 };
64 array_push(vm.frames, frame);
65 vm_interpret(&vm);
66
67 // Free resources.
68 chunk_free(main);
69 array_free(tokens);
70}
71
72#define REPL_PROMPT "bdl> "
73
74void
75run_repl(void) {
76 printf("BDL REPL (Press Ctrl-D or Ctrl-C to exit)\n");
77 while (true) {
78 printf(REPL_PROMPT);
79 StringView sv = read_line();
80 if (sv.start == NULL) {
81 return;
82 }
83 process_source(&sv);
84
85 // Check if there were any errors.
86 if (errors_n != 0 && !supress_errors) {
87 for (size_t i = 0; i < errors_n; i++) {
88 Error err = errors[i];
89 for (size_t j = 0; j < err.col + sizeof(REPL_PROMPT) - 2; j++) {
90 putchar(' ');
91 }
92 printf("|\n");
93 for (size_t j = 0; j < err.col + sizeof(REPL_PROMPT) - 2; j++) {
94 putchar(' ');
95 }
96 printf("%s\n", error_msgs[err.value]);
97 }
98 errors_n = 0;
99 continue;
100 }
101 }
102}
103
104void
105run_file(char *file_name) {
106 FILE *file = fopen(file_name, "r");
107 if (!file) {
108 fprintf(stderr, "error: couldn't open input file: %s\n", file_name);
109 exit(EXIT_FAILURE);
110 }
111
112 // Read entire file into memory.
113 fseek(file, 0, SEEK_END);
114 size_t file_size = ftell(file);
115 fseek(file, 0, SEEK_SET);
116
117 char *source = malloc(file_size + 1);
118 fread(source, 1, file_size, file);
119 source[file_size] = 0;
120
121 StringView sv = (StringView){
122 .start = source,
123 .n = file_size,
124 };
125
126 process_source(&sv);
127
128 // Check if there were any errors.
129 if (errors_n != 0 && !supress_errors) {
130 report_errors(file_name);
131 }
132
133 free(source);
134 fclose(file);
135}
136
137#define STDIN_BUF_CAP 16
138
139void
140run_stdin(void) {
141 size_t buf_size = 0;
142 char *source = NULL;
143 array_init(source, STDIN_BUF_CAP);
144
145 char c;
146 while ((c = getchar()) != EOF) {
147 array_push(source, c);
148 buf_size++;
149 }
150
151 StringView sv = (StringView){
152 .start = source,
153 .n = buf_size,
154 };
155
156 process_source(&sv);
157
158 // Check if there were any errors.
159 if (errors_n != 0 && !supress_errors) {
160 report_errors("stdin");
161 }
162
163 array_free(source);
164}
165
166#ifndef BIN_NAME
167#define BIN_NAME "bdl"
168#endif
169
170void
171print_usage(void) {
172 printf("Usage: %s [options] <filename filename ...>\n", BIN_NAME);
173 printf("\n");
174 printf("\t-i\tInteractive mode (REPL).\n");
175 printf("\n");
176}
177
178int
179main(int argc, char *argv[]) {
180 init();
181
182 int option;
183 while ((option = getopt(argc, argv, "i")) != -1) {
184 switch (option) {
185 case 'i': {
186 // Interactive mode.
187 run_repl();
188 halt();
189 return EXIT_SUCCESS;
190 } break;
191 default: {
192 print_usage();
193 return EXIT_FAILURE;
194 } break;
195 }
196 }
197
198 // Run from stdin.
199 if (optind == argc) {
200 run_stdin();
201 halt();
202 return EXIT_SUCCESS;
203 }
204
205 // Run from file.
206 while (optind < argc) {
207 char *file_name = argv[optind];
208 run_file(file_name);
209 optind++;
210 }
211
212 halt();
213 return EXIT_SUCCESS;
214}
diff --git a/src/bytecode/objects.c b/src/bytecode/objects.c
deleted file mode 100644
index c2fb989..0000000
--- a/src/bytecode/objects.c
+++ /dev/null
@@ -1,151 +0,0 @@
1#include "objects.h"
2
3Object
4make_string(StringView sv) {
5 Object obj = {
6 .type = OBJ_TYPE_STRING,
7 .text = NULL,
8 };
9 array_init(obj.text, sv.n);
10 array_insert(obj.text, sv.start, sv.n);
11 return obj;
12}
13
14Object
15make_symbol(StringView sv) {
16 Object obj = {
17 .type = OBJ_TYPE_SYMBOL,
18 .text = NULL,
19 };
20 array_init(obj.text, sv.n);
21 array_insert(obj.text, sv.start, sv.n);
22 return obj;
23}
24
25Object
26make_lambda(Chunk *chunk) {
27 Object obj = {
28 .type = OBJ_TYPE_LAMBDA,
29 };
30 obj.closure = malloc(sizeof(Closure));
31 obj.closure->chunk = chunk;
32 array_init(obj.closure->values, 0);
33 return obj;
34}
35
36void
37object_display(Object obj) {
38 switch (obj.type) {
39 case OBJ_TYPE_FIXNUM: {
40 printf("%zd", obj.fixnum);
41 } break;
42 case OBJ_TYPE_TRUE: {
43 printf("true");
44 } break;
45 case OBJ_TYPE_FALSE: {
46 printf("false");
47 } break;
48 case OBJ_TYPE_NIL: {
49 printf("()");
50 } break;
51 case OBJ_TYPE_STRING: {
52 printf("\"%.*s\"", (int)array_size(obj.text), obj.text);
53 } break;
54 case OBJ_TYPE_SYMBOL: {
55 printf(":%.*s", (int)array_size(obj.text), obj.text);
56 } break;
57 case OBJ_TYPE_PAIR: {
58 // printf("(");
59 // display_pair(obj);
60 // printf(")");
61 } break;
62 case OBJ_TYPE_LAMBDA: {
63 Chunk *chunk = obj.closure->chunk;
64 printf("#{procedure:%.*s}",
65 (int)array_size(chunk->name), chunk->name);
66 } break;
67 case OBJ_TYPE_ERR: {
68 printf("#{error}");
69 } break;
70 }
71 return;
72}
73
74void
75object_free(Object *obj) {
76 if (IS_STRING(*obj) || IS_SYMBOL(*obj)) {
77 array_free(obj->text);
78 return;
79 }
80 if (IS_LAMBDA(*obj)) {
81 Closure *closure = obj->closure;
82 for (size_t i = 0; i < array_size(closure->values); i++) {
83 object_free(&closure->values[i]);
84 }
85 array_free(closure->values);
86 // NOTE: we are leaking memory without this, we'll need a GC
87 // soon...
88 // chunk_free(closure->chunk);
89 free(closure);
90 }
91}
92
93bool
94object_equal(Object a, Object b) {
95 if (a.type != b.type) {
96 return false;
97 }
98 switch (a.type) {
99 case OBJ_TYPE_TRUE:
100 case OBJ_TYPE_FALSE: {
101 return true;
102 } break;
103 case OBJ_TYPE_FIXNUM: {
104 return a.fixnum == b.fixnum;
105 } break;
106 case OBJ_TYPE_SYMBOL:
107 case OBJ_TYPE_STRING: {
108 if (array_size(a.text) != array_size(b.text)) {
109 return false;
110 }
111 for (size_t i = 0; i < array_size(a.text); i++) {
112 if (a.text[i] != b.text[i]) {
113 return false;
114 }
115 }
116 } break;
117 case OBJ_TYPE_LAMBDA: {
118 return a.closure == b.closure;
119 } break;
120 default: {
121 return false;
122 } break;
123 }
124 return true;
125}
126
127Object
128object_copy(Object src) {
129 switch (src.type) {
130 case OBJ_TYPE_SYMBOL:
131 case OBJ_TYPE_STRING: {
132 Object copy = src;
133 copy.text = NULL;
134 array_init(copy.text, array_size(src.text));
135 array_insert(copy.text, src.text, array_size(src.text));
136 return copy;
137 } break;
138 case OBJ_TYPE_LAMBDA: {
139 // Object copy = src;
140 // StringView name = (StringView){
141 // .start = src.chunk->name,
142 // .n = array_size(src.chunk->name),
143 // };
144 // // TODO: copy full chunk?
145 // // copy.chunk = chunk_init(name);
146 // return copy;
147 } break;
148 default: { break; } break;
149 }
150 return src;
151}
diff --git a/src/bytecode/objects.h b/src/bytecode/objects.h
deleted file mode 100755
index a9a7d0f..0000000
--- a/src/bytecode/objects.h
+++ /dev/null
@@ -1,80 +0,0 @@
1#ifndef BDL_OBJECTS_H
2#define BDL_OBJECTS_H
3
4#include "string_view.h"
5#include "darray.h"
6#include "chunk.h"
7
8typedef enum ObjectType {
9 OBJ_TYPE_NIL,
10 OBJ_TYPE_TRUE,
11 OBJ_TYPE_FALSE,
12 OBJ_TYPE_FIXNUM,
13 OBJ_TYPE_SYMBOL,
14 OBJ_TYPE_STRING,
15 OBJ_TYPE_PAIR,
16 OBJ_TYPE_LAMBDA,
17 OBJ_TYPE_ERR,
18} ObjectType;
19
20typedef struct Object Object;
21
22typedef struct Closure {
23 // Non-owning reference to a chunk.
24 Chunk *chunk;
25 // Captured values for this closure.
26 Object *values;
27} Closure;
28
29// typdef struct ConsCell {
30// struct Object *car;
31// struct Object *cdr;
32// } ConsCell;
33
34typedef struct Object {
35 ObjectType type;
36 bool marked;
37 union {
38 // OBJ_TYPE_FIXNUM
39 ssize_t fixnum;
40
41 // OBJ_TYPE_STRING
42 // OBJ_TYPE_SYMBOL
43 char *text;
44
45 // OBJ_TYPE_PAIR
46 // ConsCell *cons_cell;
47
48 // OBJ_TYPE_LAMBDA
49 Closure *closure;
50 };
51} Object;
52
53Object make_string(StringView sv);
54Object make_symbol(StringView sv);
55Object make_lambda(Chunk *chunk);
56void object_display(Object obj);
57void object_free(Object *obj);
58bool object_equal(Object a, Object b);
59Object object_copy(Object src);
60
61// Value initialization.
62#define NIL_VAL ((Object){.type = OBJ_TYPE_NIL})
63#define TRUE_VAL ((Object){.type = OBJ_TYPE_TRUE})
64#define FALSE_VAL ((Object){.type = OBJ_TYPE_FALSE})
65#define FIXNUM_VAL(VAL) ((Object){.type = OBJ_TYPE_FIXNUM, .fixnum = VAL})
66#define BOOL_VAL(VAL) ((VAL) ? TRUE_VAL : FALSE_VAL)
67
68// Value extraction.
69#define AS_FIXNUM(VAL) ((VAL).fixnum)
70
71// Type checking.
72#define IS_NIL(VAL) ((VAL).type == OBJ_TYPE_NIL)
73#define IS_TRUE(VAL) ((VAL).type != OBJ_TYPE_FALSE)
74#define IS_FALSE(VAL) ((VAL).type == OBJ_TYPE_FALSE)
75#define IS_FIXNUM(VAL) ((VAL).type == OBJ_TYPE_FIXNUM)
76#define IS_STRING(VAL) ((VAL).type == OBJ_TYPE_STRING)
77#define IS_SYMBOL(VAL) ((VAL).type == OBJ_TYPE_SYMBOL)
78#define IS_LAMBDA(VAL) ((VAL).type == OBJ_TYPE_LAMBDA)
79
80#endif // BDL_OBJECTS_H
diff --git a/src/bytecode/ops.h b/src/bytecode/ops.h
deleted file mode 100755
index a43aed6..0000000
--- a/src/bytecode/ops.h
+++ /dev/null
@@ -1,46 +0,0 @@
1#ifndef BDL_OPS_H
2#define BDL_OPS_H
3
4typedef enum Ops {
5 // Load/store ops.
6 OP_CONSTANT,
7 OP_LOCAL,
8 OP_CAPTURED,
9 OP_CAPTURE_LOCAL,
10 OP_SET_CAPTURED,
11 OP_DEF_LOCAL,
12 OP_SET_LOCAL,
13 OP_DEF,
14 OP_SET,
15 OP_GET,
16 // Arithmetic ops.
17 OP_SUM,
18 OP_SUB,
19 OP_MUL,
20 OP_DIV,
21 OP_MOD,
22 // Logic ops.
23 OP_NOT,
24 OP_AND,
25 OP_OR,
26 // Numerical comparison ops.
27 OP_EQUAL,
28 OP_LESS,
29 OP_GREATER,
30 OP_LESS_EQUAL,
31 OP_GREATER_EQUAL,
32 // Jump/conditional ops.
33 OP_JUMP,
34 OP_JUMP_IF_FALSE,
35 // Display ops.
36 OP_DISPLAY,
37 OP_PRINT,
38 OP_NEWLINE,
39 // Procedures.
40 OP_CALL,
41 OP_RETURN,
42 // Clear stack after each statement.
43 OP_DROP,
44} Ops;
45
46#endif // BDL_OPS_H
diff --git a/src/bytecode/read_line.c b/src/bytecode/read_line.c
deleted file mode 100755
index 03146ad..0000000
--- a/src/bytecode/read_line.c
+++ /dev/null
@@ -1,32 +0,0 @@
1#include "read_line.h"
2
3static char readline_buf[RL_BUF_SIZE];
4
5StringView
6read_line(void) {
7 // Clear buffer.
8 for (size_t i = 0; i < RL_BUF_SIZE; i++) {
9 readline_buf[i] = 0;
10 }
11
12 // Barebones readline implementation.
13 size_t n = 0;
14 char c;
15 while ((c = getchar()) != '\n') {
16 if (c == '\b') {
17 readline_buf[n] = '\0';
18 n--;
19 } else if (c == EOF || c == '\0') {
20 return (StringView){ .start = NULL, .n = 0 };
21 } else if ((c >= ' ' && c <= '~') && n < RL_BUF_SIZE) {
22 readline_buf[n] = c;
23 n++;
24 }
25 }
26
27 StringView sv = (StringView){
28 .start = (char *)&readline_buf,
29 .n = n,
30 };
31 return sv;
32}
diff --git a/src/bytecode/read_line.h b/src/bytecode/read_line.h
deleted file mode 100755
index 160bce0..0000000
--- a/src/bytecode/read_line.h
+++ /dev/null
@@ -1,10 +0,0 @@
1#ifndef BDL_READ_LINE_H
2#define BDL_READ_LINE_H
3
4#include "string_view.h"
5
6StringView read_line(void);
7
8#define RL_BUF_SIZE 1024
9
10#endif // BDL_READ_LINE_H
diff --git a/src/bytecode/string_view.c b/src/bytecode/string_view.c
deleted file mode 100755
index 8247bd4..0000000
--- a/src/bytecode/string_view.c
+++ /dev/null
@@ -1,40 +0,0 @@
1#include "string_view.h"
2
3char
4sv_next(StringView *sv) {
5 if (sv->n == 0) {
6 return '\0';
7 }
8 char c = sv->start[0];
9 sv->start++;
10 sv->n--;
11 return c;
12}
13
14char
15sv_peek(const StringView *sv) {
16 if (sv->n == 0) {
17 return '\0';
18 }
19 return sv->start[0];
20}
21
22bool
23sv_equal(const StringView *a, const StringView *b) {
24 if (a->n != b->n) {
25 return false;
26 }
27 for (size_t i = 0; i < a->n; i++) {
28 if (a->start[i] != b->start[i]) {
29 return false;
30 }
31 }
32 return true;
33}
34
35void
36sv_write(const StringView *sv) {
37 for (size_t i = 0; i < sv->n; i++) {
38 putchar(sv->start[i]);
39 }
40}
diff --git a/src/bytecode/string_view.h b/src/bytecode/string_view.h
deleted file mode 100755
index 5977ea9..0000000
--- a/src/bytecode/string_view.h
+++ /dev/null
@@ -1,23 +0,0 @@
1#ifndef BDL_STRINGVIEW_H
2#define BDL_STRINGVIEW_H
3
4typedef struct StringView {
5 char *start;
6 size_t n;
7} StringView;
8
9// Consume a character in the stream.
10char sv_next(StringView *sv);
11
12// Check what is the current character in the stream.
13char sv_peek(const StringView *sv);
14
15// Compare if the arguments are the same.
16bool sv_equal(const StringView *a, const StringView *b);
17
18// Write a character to the given output stream.
19void sv_write(const StringView *sv);
20
21#define STRING(STR) (StringView){(STR), sizeof(STR) - 1}
22
23#endif // BDL_STRINGVIEW_H
diff --git a/src/bytecode/types.h b/src/bytecode/types.h
deleted file mode 100755
index dc21756..0000000
--- a/src/bytecode/types.h
+++ /dev/null
@@ -1,30 +0,0 @@
1#ifndef BDL_TYPES_H
2#define BDL_TYPES_H
3
4#include <stdbool.h>
5#include <stddef.h>
6#include <stdint.h>
7
8typedef uint8_t u8;
9typedef uint16_t u16;
10typedef uint32_t u32;
11typedef uint64_t u64;
12typedef int8_t s8;
13typedef int16_t s16;
14typedef int32_t s32;
15typedef int64_t s64;
16typedef volatile u8 vu8;
17typedef volatile u16 vu16;
18typedef volatile u32 vu32;
19typedef volatile u64 vu64;
20typedef volatile s8 vs8;
21typedef volatile s16 vs16;
22typedef volatile s32 vs32;
23typedef volatile s64 vs64;
24
25#define KB(N) ((u64)(N) * 1024)
26#define MB(N) ((u64)KB(N) * 1024)
27#define GB(N) ((u64)MB(N) * 1024)
28#define TB(N) ((u64)GB(N) * 1024)
29
30#endif // BDL_TYPES_H
diff --git a/src/bytecode/vm.h b/src/bytecode/vm.h
deleted file mode 100755
index d363958..0000000
--- a/src/bytecode/vm.h
+++ /dev/null
@@ -1,396 +0,0 @@
1#ifndef BDL_VM_H
2#define BDL_VM_H
3
4#include "types.h"
5#include "errors.h"
6#include "chunk.h"
7#include "ops.h"
8#include "debug.h"
9#include "hashtable.h"
10
11#define VM_FRAMES_CAP 64
12#define VM_STACK_CAP 1024
13
14typedef struct CallFrame {
15 // Current code being run.
16 Closure *closure;
17 // Return counter.
18 u8 *rp;
19 // Starting point of the locals for this procedure.
20 size_t stack_offset;
21} CallFrame;
22
23typedef struct VM {
24 CallFrame *frames;
25 // Stack.
26 Object *stack;
27 // Program counter.
28 u8 *pc;
29 // Global variables.
30 HashTable *globals;
31} VM;
32
33void vm_init(VM *vm);
34void vm_free(VM *vm);
35void vm_reset(VM *vm);
36void vm_interpret(VM *vm);
37
38void
39vm_init(VM *vm) {
40 *vm = (VM){0};
41 array_init(vm->frames, VM_FRAMES_CAP);
42 array_init(vm->stack, VM_STACK_CAP);
43 vm->globals = ht_init();
44}
45
46void
47vm_free(VM *vm) {
48 array_free(vm->frames);
49 array_free(vm->stack);
50 ht_free(vm->globals);
51}
52
53void
54vm_reset(VM *vm) {
55 vm_free(vm);
56 vm_init(vm);
57}
58
59// Helper macros for a more clear VM switch.
60#ifdef DEBUG
61#define STACK_TRACE() \
62 fprintf(stderr, "stack trace:\n"); \
63 for (ssize_t i = array_size(vm->frames) - 1; i >= 0 ; i--) { \
64 CallFrame frame = vm->frames[i]; \
65 Chunk *chunk = frame.closure->chunk; \
66 size_t instruction = vm->pc - chunk->code - 1; \
67 fprintf(stderr, "\t%-4ld -> ", i); \
68 fprintf(stderr, "%.*s",(int)array_size(chunk->name), chunk->name); \
69 fprintf(stderr, ":%ld:%ld\n", chunk->lines[instruction].line, chunk->lines[instruction].col); \
70 vm->pc = frame.rp; \
71 }
72#else
73#define STACK_TRACE()
74#endif
75
76#define RUNTIME_ERROR(ERR) \
77 error_push((Error){ \
78 .type = ERR_TYPE_RUNTIME, \
79 .value = (ERR), \
80 .line = chunk->lines[vm->pc - chunk->code - 1].line, \
81 .col = chunk->lines[vm->pc - chunk->code - 1].col, \
82 }); \
83 STACK_TRACE() \
84 return
85
86#define FIXNUM_ARITHMETIC_OP(OP) \
87 do { \
88 ssize_t n = AS_FIXNUM(array_pop(vm->stack)); \
89 size_t stack_size = array_size(vm->stack) - n; \
90 Object obj = array_peek(vm->stack, n - 1); \
91 if (!IS_FIXNUM(obj)) { \
92 RUNTIME_ERROR(ERR_WRONG_ARG_TYPE); \
93 return; \
94 } \
95 ssize_t acc = AS_FIXNUM(obj); \
96 while (n > 1) { \
97 obj = array_peek(vm->stack, n - 2); \
98 if (!IS_FIXNUM(obj)) { \
99 RUNTIME_ERROR(ERR_WRONG_ARG_TYPE); \
100 return; \
101 } \
102 ssize_t current = AS_FIXNUM(obj); \
103 acc = acc OP current; \
104 n--; \
105 } \
106 array_head(vm->stack)->size = stack_size; \
107 array_push(vm->stack, FIXNUM_VAL(acc)); \
108 } while (false)
109
110#define FIXNUM_COMPARE_OP(OP) \
111 do { \
112 ssize_t n = AS_FIXNUM(array_pop(vm->stack)); \
113 size_t stack_size = array_size(vm->stack) - n; \
114 Object obj = array_peek(vm->stack, n - 1); \
115 if (!IS_FIXNUM(obj)) { \
116 RUNTIME_ERROR(ERR_WRONG_ARG_TYPE); \
117 return; \
118 } \
119 ssize_t prev = AS_FIXNUM(obj); \
120 bool ret = true; \
121 while (n > 1) { \
122 obj = array_peek(vm->stack, n - 2); \
123 if (!IS_FIXNUM(obj)) { \
124 RUNTIME_ERROR(ERR_WRONG_ARG_TYPE); \
125 return; \
126 } \
127 ssize_t current = AS_FIXNUM(obj); \
128 ret = ret && (prev OP current); \
129 prev = current; \
130 n--; \
131 } \
132 array_head(vm->stack)->size = stack_size; \
133 array_push(vm->stack, BOOL_VAL(ret)); \
134 } while (false)
135
136#define LOGIC_OP(OP) \
137 do { \
138 ssize_t n = AS_FIXNUM(array_pop(vm->stack)); \
139 size_t stack_size = array_size(vm->stack) - n; \
140 Object obj = array_peek(vm->stack, n - 1); \
141 bool ret = IS_TRUE(obj); \
142 while (n > 1) { \
143 obj = array_peek(vm->stack, n - 2); \
144 bool current = IS_TRUE(obj); \
145 ret = ret OP current; \
146 n--; \
147 } \
148 array_head(vm->stack)->size = stack_size; \
149 array_push(vm->stack, BOOL_VAL(ret)); \
150 } while (false)
151
152void
153vm_interpret(VM *vm) {
154 CallFrame *frame = &vm->frames[0];
155 Chunk *chunk = frame->closure->chunk;
156 vm->pc = chunk->code;
157 frame->rp = NULL;
158
159 if (chunk->code == NULL || array_size(chunk->code) == 0) {
160 error_push((Error){
161 .type = ERR_TYPE_RUNTIME,
162 .value = ERR_EMPTY_CHUNK,
163 });
164 return;
165 }
166
167 while (true) {
168#ifdef DEBUG_TRACE_EXECUTION
169 printf("stack: [ ");
170 for (size_t i = 0; i < array_size(vm->stack); i++) {
171 object_display(vm->stack[i]);
172 if (i < array_size(vm->stack) - 1) {
173 printf(" | ");
174 }
175 }
176 printf(" ]\nop: ");
177 disassemble_instruction(chunk, (vm->pc - chunk->code));
178#endif
179 u8 instruction = *vm->pc++;
180 switch (instruction) {
181 case OP_LOCAL: {
182 ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
183 array_push(vm->stack, vm->stack[frame->stack_offset + idx]);
184 } break;
185 case OP_CONSTANT: {
186 u8 constant = *vm->pc++;
187 Object obj = chunk->constants[constant];
188 array_push(vm->stack, obj);
189 } break;
190 case OP_CAPTURED: {
191 ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
192 array_push(vm->stack, frame->closure->values[idx]);
193 } break;
194 case OP_CAPTURE_LOCAL: {
195 // This is a closure with captured variables. We need a copy
196 // of it that lives on the heap.
197 Object proc = array_pop(vm->stack);
198 proc = make_lambda(proc.closure->chunk);
199
200 ssize_t n_captured = AS_FIXNUM(array_pop(vm->stack));
201 for (ssize_t i = 0; i < n_captured; i++) {
202 Object value = array_pop(vm->stack);
203 array_push(proc.closure->values, value);
204 }
205 array_push(vm->stack, proc);
206 } break;
207 case OP_SET_CAPTURED: {
208 Object value = array_pop(vm->stack);
209 ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
210 frame->closure->values[idx] = value;
211 } break;
212 case OP_DEF_LOCAL: {
213 Object value = array_pop(vm->stack);
214 ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
215 vm->stack[frame->stack_offset + idx] = value;
216 } break;
217 case OP_SET_LOCAL: {
218 Object value = array_pop(vm->stack);
219 ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
220 CallFrame frame = vm->frames[array_size(vm->frames) - 1];
221 vm->stack[frame.stack_offset + idx] = value;
222 } break;
223 case OP_DEF: {
224 Object value = array_pop(vm->stack);
225 Object name = array_pop(vm->stack);
226 ht_insert(vm->globals, name, value);
227 } break;
228 case OP_SET: {
229 Object value = array_pop(vm->stack);
230 Object name = array_pop(vm->stack);
231 Object *prev = ht_lookup(vm->globals, name);
232 if (prev == NULL) {
233 RUNTIME_ERROR(ERR_SYMBOL_NOT_FOUND);
234 return;
235 }
236 ht_insert(vm->globals, name, value);
237 } break;
238 case OP_GET: {
239 Object name = array_pop(vm->stack);
240 Object *value = ht_lookup(vm->globals, name);
241 if (value == NULL) {
242 RUNTIME_ERROR(ERR_SYMBOL_NOT_FOUND);
243 return;
244 }
245 array_push(vm->stack, *value);
246 } break;
247 case OP_SUM: { FIXNUM_ARITHMETIC_OP(+); } break;
248 case OP_SUB: { FIXNUM_ARITHMETIC_OP(-); } break;
249 case OP_MUL: { FIXNUM_ARITHMETIC_OP(*); } break;
250 case OP_DIV: { FIXNUM_ARITHMETIC_OP(/); } break;
251 case OP_MOD: { FIXNUM_ARITHMETIC_OP(%); } break;
252 case OP_NOT: {
253 Object prev = array_pop(vm->stack);
254 Object new = IS_TRUE(prev) ? FALSE_VAL : TRUE_VAL;
255 array_push(vm->stack, new);
256 } break;
257 case OP_AND: { LOGIC_OP(&&); } break;
258 case OP_OR: { LOGIC_OP(||); } break;
259 case OP_EQUAL: { FIXNUM_COMPARE_OP(==); } break;
260 case OP_LESS: { FIXNUM_COMPARE_OP(<); } break;
261 case OP_GREATER: { FIXNUM_COMPARE_OP(>); } break;
262 case OP_LESS_EQUAL: { FIXNUM_COMPARE_OP(<=); } break;
263 case OP_GREATER_EQUAL: { FIXNUM_COMPARE_OP(>=); } break;
264 case OP_JUMP: {
265 u16 a = *vm->pc++;
266 u16 b = *vm->pc++;
267 s16 offset = (a << 8) | b;
268 vm->pc += offset;
269 } break;
270 case OP_JUMP_IF_FALSE: {
271 u16 a = *vm->pc++;
272 u16 b = *vm->pc++;
273 s16 offset = (a << 8) | b;
274 if (IS_FALSE(array_pop(vm->stack))) {
275 vm->pc += offset;
276 }
277 } break;
278 case OP_DISPLAY: {
279 object_display(array_pop(vm->stack));
280 } break;
281 case OP_PRINT: {
282 Object obj = array_pop(vm->stack);
283 if (!IS_STRING(obj)) {
284 RUNTIME_ERROR(ERR_WRONG_ARG_TYPE);
285 }
286 StringView scanner = (StringView) {
287 .start = obj.text,
288 .n = array_size(obj.text),
289 };
290 while (scanner.n != 0) {
291 char c = sv_next(&scanner);
292 if (c == '\\' && sv_peek(&scanner) == 'n') {
293 putchar('\n');
294 sv_next(&scanner);
295 continue;
296 }
297 if (c == '\\' && sv_peek(&scanner) == '"') {
298 putchar('"');
299 sv_next(&scanner);
300 continue;
301 }
302 putchar(c);
303 }
304 } break;
305 case OP_NEWLINE: {
306 printf("\n");
307 } break;
308 case OP_CALL: {
309 ssize_t n_args = AS_FIXNUM(array_pop(vm->stack));
310 Object proc = vm->stack[array_size(vm->stack) - 1 - n_args];
311
312 // Check the number of arguments is correct.
313 // NOTE: This is probably better handled at compilation, but for
314 // now this is simpler to implement.
315 ssize_t n_params = proc.closure->chunk->n_params;
316 ssize_t n_locals = proc.closure->chunk->n_locals - n_params;
317 if (n_args < n_params) {
318 RUNTIME_ERROR(ERR_NOT_ENOUGH_ARGS);
319 } else if (n_args > n_params) {
320 RUNTIME_ERROR(ERR_TOO_MANY_ARGS);
321 }
322
323#ifdef DEBUG
324 disassemble_chunk(proc.closure->chunk);
325 printf("n_locals: %ld\n", n_locals);
326 printf("n_params: %ld\n", n_params);
327#endif
328 // Tail-call optimization.
329 if (proc.closure->chunk != chunk || *vm->pc != OP_RETURN) {
330 // Prepare new call frame.
331 CallFrame new_frame = (CallFrame){
332 .closure = proc.closure,
333 .rp = vm->pc,
334 .stack_offset = array_size(vm->stack) - n_params,
335 };
336 array_push(vm->frames, new_frame);
337 frame = &vm->frames[array_size(vm->frames) - 1];
338 chunk = frame->closure->chunk;
339
340 // Prepare local slots.
341 for (ssize_t i = 0; i < n_locals; i++) {
342 array_push(vm->stack, NIL_VAL);
343 }
344 } else {
345 // Bind tail-call parameters.
346 for (ssize_t i = 0; i < n_params; i++) {
347 size_t offset = n_locals + n_params - 1 - i;
348 Object obj = array_peek(vm->stack, offset);
349 vm->stack[frame->stack_offset + i] = obj;
350 }
351
352 // Reset stack size.
353 size_t offset = frame->stack_offset + n_params + n_locals;
354 array_head(vm->stack)->size = offset;
355 }
356 vm->pc = chunk->code;
357 } break;
358 case OP_RETURN: {
359 if (frame->rp == NULL) {
360 Object ret = array_pop(vm->stack);
361 if (!IS_NIL(ret)) {
362 object_display(ret);
363 printf("\n");
364 }
365 return;
366 }
367 vm->pc = frame->rp;
368 array_head(vm->frames)->size--;
369 Object ret = array_pop(vm->stack);
370 array_head(vm->stack)->size = frame->stack_offset - 1;
371 array_push(vm->stack, ret);
372 frame = &vm->frames[array_size(vm->frames) - 1];
373 chunk = frame->closure->chunk;
374 } break;
375 case OP_DROP: {
376 array_head(vm->stack)->size = 0;
377 } break;
378 default: {
379 RUNTIME_ERROR(ERR_NOT_IMPLEMENTED);
380 } break;
381 }
382 }
383
384 error_push((Error){
385 .type = ERR_TYPE_RUNTIME,
386 .value = ERR_PC_OOB,
387 .line = chunk->lines[0].line,
388 .col = chunk->lines[0].col,
389 });
390}
391
392#undef FIXNUM_ARITHMETIC_OP
393#undef FIXNUM_COMPARE_OP
394#undef LOGIC_OP
395
396#endif // BDL_VM_H
diff --git a/src/errors.c b/src/errors.c
index 11348fd..efc834f 100644
--- a/src/errors.c
+++ b/src/errors.c
@@ -3,44 +3,42 @@
3static const char* error_msgs[] = { 3static const char* error_msgs[] = {
4 [ERR_UNKNOWN] = "error: something unexpected happened", 4 [ERR_UNKNOWN] = "error: something unexpected happened",
5 [ERR_UNMATCHED_STRING] = "error: unmatched string delimiter", 5 [ERR_UNMATCHED_STRING] = "error: unmatched string delimiter",
6 [ERR_UNBALANCED_PAREN] = "error: unbalanced parentheses", 6 [ERR_UNKNOWN_TOK_TYPE] = "error: unknown token type",
7 [ERR_NOT_IMPLEMENTED] = "error: not implemented", 7 [ERR_MALFORMED_NUMBER] = "error: malformed number token",
8 [ERR_EOF_REACHED] = "error: EOF reached",
9 [ERR_UNKNOWN_TOKEN] = "error: unknown token",
10 [ERR_UNKNOWN_OBJ_TYPE] = "error: can't eval unknown object type",
11 [ERR_NOT_A_SYMBOL] = "error: object is not a symbol",
12 [ERR_SYMBOL_NOT_FOUND] = "error: symbol not found",
13 [ERR_NOT_CALLABLE] = "error: not callable",
14 [ERR_NOT_ENOUGH_ARGS] = "error: not enough arguments",
15 [ERR_TOO_MANY_ARGS] = "error: too many arguments",
16 [ERR_WRONG_ARG_TYPE] = "error: wrong argument type",
17 [ERR_DIVISION_BY_ZERO] = "error: division by zero",
18 [ERR_AMBIGUOUS_PARAMS] = "error: ambiguous parameter names",
19}; 8};
20 9
10static Error current_error = {.value = ERR_OK};
11
21void 12void
22error_push(Errors *errors, Error error) { 13push_error(ErrorType type, ErrorValue value, size_t line, size_t col) {
23 if (errors->n < ERR_MAX_NUMBER) { 14 if (has_errors()) {
24 errors->errors[errors->n++] = error; 15 return;
25 } 16 }
17 current_error.type = type;
18 current_error.value = value;
19 current_error.line = line;
20 current_error.col = col;
21}
22
23bool
24has_errors(void) {
25 return current_error.value != ERR_OK;
26} 26}
27 27
28void 28void
29report_errors(Errors *errors, const char *file_name) { 29check_errors(const char *file_name) {
30 for (size_t i = 0; i < errors->n; i++) { 30 if (!has_errors()) {
31 Error err = errors->errors[i]; 31 return;
32 fprintf(stderr, "%s", file_name); 32 }
33 if (err.line != 0) { 33 fprintf(stderr, "%s", file_name);
34 fprintf(stderr, ":%ld:%ld", err.line, err.col); 34 if (current_error.line != 0) {
35 } 35 fprintf(stderr, ":%ld:%ld", current_error.line, current_error.col);
36 switch (err.type) { 36 }
37 case ERR_TYPE_LEXER: { fprintf(stderr, ": [lexer]"); } break; 37 switch (current_error.type) {
38 case ERR_TYPE_COMPILER: { fprintf(stderr, ": [compiler]"); } break; 38 case ERR_TYPE_LEXER: { fprintf(stderr, ": [lexer] "); } break;
39 case ERR_TYPE_RUNTIME: { fprintf(stderr, ": [runtime]"); } break; 39 case ERR_TYPE_PARSER: { fprintf(stderr, ": [parser] "); } break;
40 case ERR_TYPE_PARSER: { fprintf(stderr, ": [parser]"); } break; 40 default: break;
41 default: break;
42 }
43 fprintf(stderr, " %s\n", error_msgs[err.value]);
44 } 41 }
45 errors->n = 0; 42 fprintf(stderr, "%s\n", error_msgs[current_error.value]);
43 exit(EXIT_FAILURE);
46} 44}
diff --git a/src/errors.h b/src/errors.h
index 7d8e977..8a378a2 100644
--- a/src/errors.h
+++ b/src/errors.h
@@ -6,26 +6,14 @@
6typedef enum ErrorType { 6typedef enum ErrorType {
7 ERR_TYPE_LEXER, 7 ERR_TYPE_LEXER,
8 ERR_TYPE_PARSER, 8 ERR_TYPE_PARSER,
9 ERR_TYPE_COMPILER,
10 ERR_TYPE_RUNTIME,
11} ErrorType; 9} ErrorType;
12 10
13typedef enum ErrorValue { 11typedef enum ErrorValue {
14 ERR_UNKNOWN = 0, 12 ERR_UNKNOWN = 0,
15 ERR_UNMATCHED_STRING, 13 ERR_UNMATCHED_STRING,
16 ERR_UNBALANCED_PAREN, 14 ERR_UNKNOWN_TOK_TYPE,
17 ERR_NOT_IMPLEMENTED, 15 ERR_MALFORMED_NUMBER,
18 ERR_EOF_REACHED, 16 ERR_OK,
19 ERR_UNKNOWN_TOKEN,
20 ERR_UNKNOWN_OBJ_TYPE,
21 ERR_NOT_A_SYMBOL,
22 ERR_SYMBOL_NOT_FOUND,
23 ERR_NOT_CALLABLE,
24 ERR_NOT_ENOUGH_ARGS,
25 ERR_TOO_MANY_ARGS,
26 ERR_WRONG_ARG_TYPE,
27 ERR_DIVISION_BY_ZERO,
28 ERR_AMBIGUOUS_PARAMS,
29} ErrorValue; 17} ErrorValue;
30 18
31typedef struct Error { 19typedef struct Error {
@@ -35,14 +23,8 @@ typedef struct Error {
35 size_t col; 23 size_t col;
36} Error; 24} Error;
37 25
38#define ERR_MAX_NUMBER 16 26void push_error(ErrorType type, ErrorValue value, size_t line, size_t col);
39 27void check_errors(const char *file_name);
40typedef struct Errors { 28bool has_errors(void);
41 Error errors[ERR_MAX_NUMBER];
42 size_t n;
43} Errors;
44
45void error_push(Errors *errors, Error error);
46void report_errors(Errors *errors, const char *file_name);
47 29
48#endif // BDL_ERRORS_H 30#endif // BDL_ERRORS_H
diff --git a/src/lexer.c b/src/lexer.c
index 09c8f6c..56b670b 100644
--- a/src/lexer.c
+++ b/src/lexer.c
@@ -5,7 +5,11 @@ static const char* token_str[] = {
5 [TOKEN_UNKNOWN] = "TOKEN_UNKNOWN", 5 [TOKEN_UNKNOWN] = "TOKEN_UNKNOWN",
6 [TOKEN_LPAREN] = "TOKEN_LPAREN", 6 [TOKEN_LPAREN] = "TOKEN_LPAREN",
7 [TOKEN_RPAREN] = "TOKEN_RPAREN", 7 [TOKEN_RPAREN] = "TOKEN_RPAREN",
8 [TOKEN_FIXNUM] = "TOKEN_FIXNUM", 8 [TOKEN_LSQUARE] = "TOKEN_LSQUARE",
9 [TOKEN_RSQUARE] = "TOKEN_RSQUARE",
10 [TOKEN_LCURLY] = "TOKEN_LCURLY",
11 [TOKEN_RCURLY] = "TOKEN_RCURLY",
12 [TOKEN_NUMBER] = "TOKEN_NUMBER",
9 [TOKEN_SYMBOL] = "TOKEN_SYMBOL", 13 [TOKEN_SYMBOL] = "TOKEN_SYMBOL",
10 [TOKEN_STRING] = "TOKEN_STRING", 14 [TOKEN_STRING] = "TOKEN_STRING",
11 [TOKEN_NIL] = "TOKEN_NIL", 15 [TOKEN_NIL] = "TOKEN_NIL",
@@ -16,6 +20,10 @@ static const char* token_str[] = {
16 [TOKEN_DEF] = "TOKEN_DEF", 20 [TOKEN_DEF] = "TOKEN_DEF",
17 [TOKEN_SET] = "TOKEN_SET", 21 [TOKEN_SET] = "TOKEN_SET",
18 [TOKEN_FUN] = "TOKEN_FUN", 22 [TOKEN_FUN] = "TOKEN_FUN",
23 [TOKEN_STRUCT] = "TOKEN_STRUCT",
24 [TOKEN_COLON] = "TOKEN_COLON",
25 [TOKEN_DOT] = "TOKEN_DOT",
26 [TOKEN_AT] = "TOKEN_AT",
19 [TOKEN_EOF] = "TOKEN_EOF", 27 [TOKEN_EOF] = "TOKEN_EOF",
20}; 28};
21 29
@@ -24,14 +32,8 @@ print_token(Token tok) {
24 printf("[%4ld:%-4ld] ", tok.line, tok.col); 32 printf("[%4ld:%-4ld] ", tok.line, tok.col);
25 printf("%s", token_str[tok.type]); 33 printf("%s", token_str[tok.type]);
26 switch (tok.type) { 34 switch (tok.type) {
27 case TOKEN_FIXNUM: { 35 case TOKEN_NUMBER:
28 printf(" -> "); 36 case TOKEN_SYMBOL:
29 sv_write(&tok.value);
30 } break;
31 case TOKEN_SYMBOL: {
32 printf(" -> ");
33 sv_write(&tok.value);
34 } break;
35 case TOKEN_STRING: { 37 case TOKEN_STRING: {
36 printf(" -> "); 38 printf(" -> ");
37 sv_write(&tok.value); 39 sv_write(&tok.value);
@@ -55,6 +57,12 @@ scan_next(Scanner *scanner) {
55 return c; 57 return c;
56} 58}
57 59
60void
61scan_rewind(Scanner *scanner) {
62 sv_rewind(&scanner->current);
63 scanner->offset--;
64}
65
58char 66char
59scan_peek(const Scanner *scanner) { 67scan_peek(const Scanner *scanner) {
60 return sv_peek(&scanner->current); 68 return sv_peek(&scanner->current);
@@ -95,6 +103,12 @@ is_delimiter(char c) {
95 case '\'': 103 case '\'':
96 case '(': 104 case '(':
97 case ')': 105 case ')':
106 case '[':
107 case ']':
108 case '{':
109 case '}':
110 case ':':
111 case '@':
98 case ' ': 112 case ' ':
99 case '\f': 113 case '\f':
100 case '\n': 114 case '\n':
@@ -110,22 +124,65 @@ is_delimiter(char c) {
110#define TOKEN_IS_KEYWORD(VAL, KEYWORD) \ 124#define TOKEN_IS_KEYWORD(VAL, KEYWORD) \
111 sv_equal(&(VAL), &(StringView){(KEYWORD), sizeof(KEYWORD) - 1}) 125 sv_equal(&(VAL), &(StringView){(KEYWORD), sizeof(KEYWORD) - 1})
112 126
113TokenType 127size_t
114find_primitive_type(const StringView value) { 128scan_number_token(Scanner *scanner) {
115 bool is_fixnum = true; 129 char first = scan_next(scanner);
116 for (size_t i = 0; i < value.n; i++) { 130 char second = scan_peek(scanner);
117 char c = value.start[i]; 131 size_t n = 1;
118 if (i == 0 && c == '-' && value.n > 1) { 132 if (first == '0' && !is_delimiter(second)) {
119 continue; 133 if (second == 'x') {
120 } 134 // Hex constant.
121 if (!(c >= '0' && c <= '9')) { 135 scan_next(scanner);
122 is_fixnum = false; 136 n++;
123 break; 137 if (is_delimiter(scan_peek(scanner))) {
138 return 0;
139 }
140 while (!is_delimiter(scan_peek(scanner))) {
141 char c = scan_next(scanner);
142 if (!(c >= '0' && c <= '9') &&
143 !(c >= 'a' && c <= 'f') &&
144 !(c >= 'A' && c <= 'F')) {
145 return 0;
146 }
147 n++;
148 }
149 return n;
150 } else if (second == 'b') {
151 // Binary constant.
152 scan_next(scanner);
153 n++;
154 if (is_delimiter(scan_peek(scanner))) {
155 return 0;
156 }
157 while (!is_delimiter(scan_peek(scanner))) {
158 char c = scan_next(scanner);
159 if (!(c == '0' || c == '1')) {
160 return 0;
161 }
162 n++;
163 }
124 } 164 }
125 } 165 }
126 if (is_fixnum) { 166
127 return TOKEN_FIXNUM; 167 // Decimal number or floating point.
168 bool has_dot = false;
169 while (!is_delimiter(scan_peek(scanner))) {
170 char c = scan_next(scanner);
171 if (c == '.') {
172 if (has_dot) {
173 return 0;
174 }
175 has_dot = true;
176 } else if (!(c >= '0' && c <= '9')) {
177 return 0;
178 }
179 n++;
128 } 180 }
181 return n;
182}
183
184TokenType
185find_token_type(const StringView value) {
129 if (TOKEN_IS_KEYWORD(value, "nil")) { return TOKEN_NIL; } 186 if (TOKEN_IS_KEYWORD(value, "nil")) { return TOKEN_NIL; }
130 if (TOKEN_IS_KEYWORD(value, "true")) { return TOKEN_TRUE; } 187 if (TOKEN_IS_KEYWORD(value, "true")) { return TOKEN_TRUE; }
131 if (TOKEN_IS_KEYWORD(value, "false")) { return TOKEN_FALSE; } 188 if (TOKEN_IS_KEYWORD(value, "false")) { return TOKEN_FALSE; }
@@ -134,12 +191,20 @@ find_primitive_type(const StringView value) {
134 if (TOKEN_IS_KEYWORD(value, "def")) { return TOKEN_DEF; } 191 if (TOKEN_IS_KEYWORD(value, "def")) { return TOKEN_DEF; }
135 if (TOKEN_IS_KEYWORD(value, "set!")) { return TOKEN_SET; } 192 if (TOKEN_IS_KEYWORD(value, "set!")) { return TOKEN_SET; }
136 if (TOKEN_IS_KEYWORD(value, "fun")) { return TOKEN_FUN; } 193 if (TOKEN_IS_KEYWORD(value, "fun")) { return TOKEN_FUN; }
194 if (TOKEN_IS_KEYWORD(value, "struct")) { return TOKEN_STRUCT; }
137 195
138 return TOKEN_SYMBOL; 196 return TOKEN_SYMBOL;
139} 197}
140 198
199void
200print_tokens(Token *tokens) {
201 for (size_t i = 0; i < array_size(tokens); i++) {
202 print_token(tokens[i]);
203 }
204}
205
141Token * 206Token *
142tokenize(const StringView *sv, Errors *errors) { 207tokenize(const StringView *sv) {
143 Token *tokens = NULL; 208 Token *tokens = NULL;
144 array_init(tokens, 1); 209 array_init(tokens, 1);
145 Scanner scanner = (Scanner){ 210 Scanner scanner = (Scanner){
@@ -153,10 +218,16 @@ tokenize(const StringView *sv, Errors *errors) {
153 size_t line = scanner.line_number; 218 size_t line = scanner.line_number;
154 size_t col = scanner.col_number; 219 size_t col = scanner.col_number;
155 size_t offset = scanner.offset; 220 size_t offset = scanner.offset;
221 Token token = (Token){
222 .type = TOKEN_UNKNOWN,
223 .line = line,
224 .col = col,
225 };
156 char c = scan_next(&scanner); 226 char c = scan_next(&scanner);
157 switch (c) { 227 switch (c) {
158 case ';': { 228 case ';': {
159 while ((c = scan_next(&scanner)) != '\n' && c != '\0') {} 229 while ((c = scan_next(&scanner)) != '\n' && c != '\0') {}
230 continue;
160 } break; 231 } break;
161 case '"': { 232 case '"': {
162 char prev = c; 233 char prev = c;
@@ -172,73 +243,66 @@ tokenize(const StringView *sv, Errors *errors) {
172 n++; 243 n++;
173 } 244 }
174 if (!found) { 245 if (!found) {
175 error_push(errors, (Error){ 246 push_error(ERR_TYPE_LEXER, ERR_UNMATCHED_STRING, line, col);
176 .type = ERR_TYPE_LEXER,
177 .value = ERR_UNMATCHED_STRING,
178 .line = line,
179 .col = col,
180 });
181 return tokens; 247 return tokens;
182 } 248 }
183 Token token = (Token){ 249 token.value = (StringView){
184 .value = (StringView){ 250 .start = &sv->start[offset + 1],
185 .start = &sv->start[offset + 1], 251 .n = n,
186 .n = n,
187 },
188 .type = TOKEN_STRING,
189 .line = line,
190 .col = col,
191 };
192 array_push(tokens, token);
193 } break;
194 case '(': {
195 if (scan_peek(&scanner) == ')') {
196 scan_next(&scanner);
197 Token token = (Token){
198 .type = TOKEN_NIL,
199 .line = line,
200 .col = col,
201 };
202 array_push(tokens, token);
203 } else {
204 Token token = (Token){
205 .type = TOKEN_LPAREN,
206 .line = line,
207 .col = col,
208 };
209 array_push(tokens, token);
210 }
211 } break;
212 case ')': {
213 Token token = (Token){
214 .type = TOKEN_RPAREN,
215 .line = line,
216 .col = col,
217 }; 252 };
218 array_push(tokens, token); 253 token.type = TOKEN_STRING;
219 } break; 254 } break;
255 case '(': { token.type = TOKEN_LPAREN; } break;
256 case ')': { token.type = TOKEN_RPAREN; } break;
257 case '[': { token.type = TOKEN_LSQUARE; } break;
258 case ']': { token.type = TOKEN_RSQUARE; } break;
259 case '{': { token.type = TOKEN_LCURLY; } break;
260 case '}': { token.type = TOKEN_RCURLY; } break;
261 case ':': { token.type = TOKEN_COLON; } break;
262 case '.': { token.type = TOKEN_DOT; } break;
263 case '@': { token.type = TOKEN_AT; } break;
220 default: { 264 default: {
221 size_t n = 1; 265 size_t n = 1;
222 while (!is_delimiter(scan_peek(&scanner))) { 266 if (c == '-' && !is_delimiter(scan_peek(&scanner))) {
223 scan_next(&scanner); 267 n += scan_number_token(&scanner);
224 n++; 268 token.value = (StringView){
225 }
226 if (c == EOF || c == '\0') {
227 break;
228 }
229 Token token = (Token){
230 .value = (StringView){
231 .start = &sv->start[offset], 269 .start = &sv->start[offset],
232 .n = n, 270 .n = n,
233 }, 271 };
234 .type = TOKEN_SYMBOL, 272 token.type = TOKEN_NUMBER;
235 .line = line, 273 } else if (c >= '0' && c <= '9') {
236 .col = col, 274 scan_rewind(&scanner);
237 }; 275 n = scan_number_token(&scanner);
238 token.type = find_primitive_type(token.value); 276 if (n == 0) {
239 array_push(tokens, token); 277 push_error(ERR_TYPE_LEXER, ERR_MALFORMED_NUMBER, line, col);
278 return tokens;
279 }
280 token.value = (StringView){
281 .start = &sv->start[offset],
282 .n = n,
283 };
284 token.type = TOKEN_NUMBER;
285 } else {
286 while (!is_delimiter(scan_peek(&scanner))) {
287 if (scan_peek(&scanner) == '.') {
288 break;
289 }
290 c = scan_next(&scanner);
291 n++;
292 }
293 token.value = (StringView){
294 .start = &sv->start[offset],
295 .n = n,
296 };
297 token.type = find_token_type(token.value);
298 }
240 } break; 299 } break;
241 } 300 }
301 if (token.type == TOKEN_UNKNOWN) {
302 push_error(ERR_TYPE_LEXER, ERR_UNKNOWN_TOK_TYPE, line, col);
303 return tokens;
304 }
305 array_push(tokens, token);
242 } 306 }
243 307
244 // Push EOF token. 308 // Push EOF token.
diff --git a/src/lexer.h b/src/lexer.h
index c477fbd..d864a1d 100644
--- a/src/lexer.h
+++ b/src/lexer.h
@@ -9,9 +9,13 @@ typedef enum TokenType {
9 // Parentheses. 9 // Parentheses.
10 TOKEN_LPAREN, 10 TOKEN_LPAREN,
11 TOKEN_RPAREN, 11 TOKEN_RPAREN,
12 TOKEN_LSQUARE,
13 TOKEN_RSQUARE,
14 TOKEN_LCURLY,
15 TOKEN_RCURLY,
12 16
13 // Primitive types. 17 // Primitive types.
14 TOKEN_FIXNUM, 18 TOKEN_NUMBER,
15 TOKEN_SYMBOL, 19 TOKEN_SYMBOL,
16 TOKEN_STRING, 20 TOKEN_STRING,
17 TOKEN_NIL, 21 TOKEN_NIL,
@@ -24,6 +28,12 @@ typedef enum TokenType {
24 TOKEN_DEF, 28 TOKEN_DEF,
25 TOKEN_SET, 29 TOKEN_SET,
26 TOKEN_FUN, 30 TOKEN_FUN,
31 TOKEN_STRUCT,
32
33 // Special operators.
34 TOKEN_COLON,
35 TOKEN_DOT,
36 TOKEN_AT,
27 37
28 // End of file. 38 // End of file.
29 TOKEN_EOF, 39 TOKEN_EOF,
@@ -46,8 +56,8 @@ typedef struct Scanner {
46// Print a token to standard output for debugging purposes. 56// Print a token to standard output for debugging purposes.
47void print_token(Token tok); 57void print_token(Token tok);
48 58
49// Same functionality as the ScanView pairs, but keeping track of line and 59// Same functionality as with StringView, but keeping track of line and column
50// column numbers. 60// numbers.
51char scan_next(Scanner *scanner); 61char scan_next(Scanner *scanner);
52char scan_peek(const Scanner *scanner); 62char scan_peek(const Scanner *scanner);
53 63
@@ -61,9 +71,12 @@ void skip_whitespace(Scanner *scanner);
61bool is_delimiter(char c); 71bool is_delimiter(char c);
62 72
63// Extract the token type from the current string. 73// Extract the token type from the current string.
64TokenType find_primitive_type(const StringView value); 74TokenType find_token_type(const StringView value);
65 75
66// Generate a list of tokens from the given string. 76// Generate a list of tokens from the given string.
67Token * tokenize(const StringView *sv, Errors *errors); 77Token * tokenize(const StringView *sv);
78
79// Display tokens from token list.
80void print_tokens(Token *tokens);
68 81
69#endif // BDL_LEXER_H 82#endif // BDL_LEXER_H
diff --git a/src/main.c b/src/main.c
index 30eab2b..17dd481 100644
--- a/src/main.c
+++ b/src/main.c
@@ -7,8 +7,8 @@
7#include "string_view.c" 7#include "string_view.c"
8#include "errors.c" 8#include "errors.c"
9#include "lexer.c" 9#include "lexer.c"
10#include "parser.c" 10// #include "parser.c"
11#include "ir.h" 11// #include "ir.h"
12// #include "compiler.h" 12// #include "compiler.h"
13 13
14void 14void
@@ -23,34 +23,32 @@ halt(void) {
23 23
24void 24void
25process_source(const StringView *source, const char *file_name) { 25process_source(const StringView *source, const char *file_name) {
26 Errors errors = {0};
27
28 // Read tokens. 26 // Read tokens.
29 Token *tokens = tokenize(source, &errors); 27 Token *tokens = tokenize(source);
30 if (errors.n != 0) { 28 print_tokens(tokens);
31 report_errors(&errors, file_name); 29 check_errors(file_name);
32 array_free(tokens); 30 // if (errors.n != 0) {
33 exit(EXIT_FAILURE); 31 // exit(EXIT_FAILURE);
34 } 32 // }
35 33
36 // Parser. 34 // // Parser.
37 Program program = parse(tokens, &errors); 35 // Program program = parse(tokens, &errors);
38 if (errors.n != 0) { 36 // if (errors.n != 0) {
39 report_errors(&errors, file_name); 37 // report_errors(&errors, file_name);
40 free_objects(); 38 // free_objects();
41 array_free(tokens); 39 // array_free(tokens);
42 exit(EXIT_FAILURE); 40 // exit(EXIT_FAILURE);
43 } 41 // }
44 array_free(tokens); 42 // array_free(tokens);
45 43
46 // TODO: Optimization. 44 // // TODO: Optimization.
47 45
48 // Compilation. 46 // // Compilation.
49 ProgramIr program_ir = compile(program); 47 // ProgramIr program_ir = compile(program);
50 (void)program_ir; 48 // (void)program_ir;
51 49
52 // Free resources. 50 // // Free resources.
53 free_objects(); 51 // free_objects();
54} 52}
55 53
56void 54void
diff --git a/src/string_view.c b/src/string_view.c
index 8247bd4..4e9df5c 100644
--- a/src/string_view.c
+++ b/src/string_view.c
@@ -11,6 +11,15 @@ sv_next(StringView *sv) {
11 return c; 11 return c;
12} 12}
13 13
14void
15sv_rewind(StringView *sv) {
16 if (sv->start == 0) {
17 return;
18 }
19 sv->start--;
20 sv->n++;
21}
22
14char 23char
15sv_peek(const StringView *sv) { 24sv_peek(const StringView *sv) {
16 if (sv->n == 0) { 25 if (sv->n == 0) {
diff --git a/src/string_view.h b/src/string_view.h
index 4dbbaaf..cb0f488 100644
--- a/src/string_view.h
+++ b/src/string_view.h
@@ -11,6 +11,9 @@ typedef struct StringView {
11// Consume a character in the stream. 11// Consume a character in the stream.
12char sv_next(StringView *sv); 12char sv_next(StringView *sv);
13 13
14// Rewind a character in the stream.
15void sv_rewind(StringView *sv);
16
14// Check what is the current character in the stream. 17// Check what is the current character in the stream.
15char sv_peek(const StringView *sv); 18char sv_peek(const StringView *sv);
16 19
diff --git a/src/treewalk/darray.h b/src/treewalk/darray.h
deleted file mode 100644
index db6234d..0000000
--- a/src/treewalk/darray.h
+++ /dev/null
@@ -1,78 +0,0 @@
1#ifndef BDL_DARRAY_H
2#define BDL_DARRAY_H
3
4#include <string.h>
5
6typedef struct ArrayHeader {
7 size_t size;
8 size_t cap;
9} ArrayHeader;
10
11// Header/Size/capacity accessors.
12#define array_head(ARR) ((ArrayHeader *)((char *)(ARR) - sizeof(ArrayHeader)))
13#define array_size(ARR) ((ARR) ? array_head(ARR)->size : 0)
14#define array_cap(ARR) ((ARR) ? array_head(ARR)->cap : 0)
15
16// Initialize a dynamic array ARR with N elements. The initialization doesn't
17// zero out the data, so thread carefully..
18#define array_init(ARR,N) ((ARR) = _array_reserve(N, sizeof(*(ARR))))
19
20// Push a given element T to the dynamic array ARR.
21#define array_push(ARR, T) \
22 ((ARR) = _array_maybe_grow(ARR, sizeof(T)), \
23 (ARR)[array_head(ARR)->size++] = (T))
24
25// Return the last element of the array. Can be used to build stacks.
26#define array_pop(ARR) (ARR)[--array_head(ARR)->size]
27
28// Insert N bytes from the SRC array into the ARR dynamic array.
29#define array_insert(ARR, SRC, N) \
30 ((ARR) = _array_insert(ARR, SRC, N, sizeof(*(ARR))))
31
32// Free the memory from the original allocated position.
33#define array_free(ARR) ((ARR) ? free(array_head(ARR)), (ARR) = NULL : 0)
34
35static inline void *
36_array_reserve(size_t num_elem, size_t type_size) {
37 char *p = malloc(num_elem * type_size + sizeof(ArrayHeader));
38 p += sizeof(ArrayHeader);
39 array_head(p)->size = 0;
40 array_head(p)->cap = num_elem;
41 return p;
42}
43
44static inline void *
45_array_maybe_grow(void *arr, size_t type_size) {
46 ArrayHeader *head = array_head(arr);
47 if (head->cap == head->size) {
48 if (head->cap == 0) {
49 head->cap++;
50 } else {
51 head->cap *= 2;
52 }
53 head = realloc(head, head->cap * type_size + sizeof(ArrayHeader));
54 }
55 arr = (char *)head + sizeof(ArrayHeader);
56 return arr;
57}
58
59static inline
60char * _array_insert(char *arr, const char *src, size_t n_bytes, size_t type_size) {
61 ArrayHeader *head = array_head(arr);
62 size_t new_size = n_bytes + head->size;
63 if (new_size >= head->cap * type_size) {
64 if (head->cap == 0) {
65 head->cap = 1;
66 }
67 while (new_size >= head->cap * type_size) {
68 head->cap *= 2;
69 }
70 head = realloc(head, head->cap * type_size + sizeof(ArrayHeader));
71 }
72 arr = (char *)head + sizeof(ArrayHeader);
73 memcpy((arr + head->size), src, n_bytes);
74 head->size = new_size;
75 return arr;
76}
77
78#endif // BDL_DARRAY_H
diff --git a/src/treewalk/environment.c b/src/treewalk/environment.c
deleted file mode 100644
index dd4a648..0000000
--- a/src/treewalk/environment.c
+++ /dev/null
@@ -1,72 +0,0 @@
1#include "environment.h"
2#include "gc.h"
3#include "errors.h"
4
5Environment *
6env_create(Environment *parent) {
7 Environment *env = alloc_env();
8 env->parent = parent;
9 env->marked = false;
10 env->table = ht_init();
11 return env;
12}
13
14void
15env_add_symbol(Environment *env, Object *symbol, Object *value) {
16 if (symbol->type != OBJ_TYPE_SYMBOL) {
17 error_push((Error){
18 .type = ERR_TYPE_RUNTIME,
19 .value = ERR_NOT_A_SYMBOL,
20 .line = 0,
21 .col = 0,
22 });
23 return;
24 }
25 ht_insert(env->table, symbol, value);
26}
27
28Object *
29env_lookup(Environment *env, Object *symbol) {
30 while (env != NULL) {
31 Object *obj = ht_lookup(env->table, symbol);
32 if (obj != NULL) {
33 return obj;
34 }
35 env = env->parent;
36 }
37 return obj_err;
38}
39
40Object *
41env_update(Environment *env, Object *symbol, Object *value) {
42 while (env != NULL) {
43 Object *obj = ht_lookup(env->table, symbol);
44 if (obj != NULL) {
45 ht_insert(env->table, symbol, value);
46 return obj_nil;
47 }
48 env = env->parent;
49 }
50 error_push((Error){
51 .type = ERR_TYPE_RUNTIME,
52 .value = ERR_SYMBOL_NOT_FOUND,
53 });
54 return obj_err;
55}
56
57void
58env_add_or_update_current(Environment *env, Object *symbol, Object *value) {
59 ht_insert(env->table, symbol, value);
60}
61
62Environment *
63env_extend(Environment *parent, Environment *extra) {
64 Environment *env = parent;
65 HashTablePair *pairs = extra->table->pairs;
66 for (size_t i = 0; i < array_cap(pairs); i++) {
67 if (pairs[i].key != NULL) {
68 ht_insert(env->table, pairs[i].key, pairs[i].value);
69 }
70 }
71 return env;
72}
diff --git a/src/treewalk/environment.h b/src/treewalk/environment.h
deleted file mode 100644
index 5ee21ad..0000000
--- a/src/treewalk/environment.h
+++ /dev/null
@@ -1,27 +0,0 @@
1#ifndef BDL_ENVIRONMENT_H
2#define BDL_ENVIRONMENT_H
3
4#include "objects.h"
5
6typedef struct Environment {
7 struct Environment *parent;
8 HashTable *table;
9 bool marked;
10} Environment;
11
12Environment * env_create(Environment *parent);
13void env_add_symbol(Environment *env, Object *symbol, Object *value);
14Object * env_lookup(Environment *env, Object *symbol);
15Object * env_update(Environment *env, Object *symbol, Object *value);
16ssize_t env_index_current(Environment *env, Object *symbol);
17void env_add_or_update_current(Environment *env, Object *symbol, Object *value);
18Environment * env_extend(Environment *parent, Environment *extra);
19
20#define MAKE_ENV_VAR(ENV,STR,VAR) \
21 (env_add_symbol((ENV), MAKE_SYM(STR), (VAR)))
22#define MAKE_ENV_PROC(ENV,STR,FUN) \
23 (env_add_symbol((ENV), MAKE_SYM(STR), make_procedure(FUN)))
24
25#define ENV_BUF_CAP 8
26
27#endif // BDL_ENVIRONMENT_H
diff --git a/src/treewalk/errors.c b/src/treewalk/errors.c
deleted file mode 100644
index d957cfa..0000000
--- a/src/treewalk/errors.c
+++ /dev/null
@@ -1,29 +0,0 @@
1#include "errors.h"
2
3static const char* error_msgs[] = {
4 [ERR_UNKNOWN] = "error: something unexpected happened",
5 [ERR_UNMATCHED_STRING] = "error: unmatched string delimiter",
6 [ERR_UNBALANCED_PAREN] = "error: unbalanced parentheses",
7 [ERR_NOT_IMPLEMENTED] = "error: not implemented",
8 [ERR_EOF_REACHED] = "error: EOF reached",
9 [ERR_UNKNOWN_TOKEN] = "error: unknown token",
10 [ERR_UNKNOWN_OBJ_TYPE] = "error: can't eval unknown object type",
11 [ERR_NOT_A_SYMBOL] = "error: object is not a symbol",
12 [ERR_SYMBOL_NOT_FOUND] = "error: symbol not found",
13 [ERR_OBJ_NOT_CALLABLE] = "error: object is not callable",
14 [ERR_NOT_ENOUGH_ARGS] = "error: not enough arguments",
15 [ERR_TOO_MANY_ARGS] = "error: too many arguments",
16 [ERR_WRONG_ARG_TYPE] = "error: wrong argument type",
17 [ERR_DIVISION_BY_ZERO] = "error: division by zero",
18};
19
20static Error errors[ERR_MAX_NUMBER];
21static size_t errors_n = 0;
22static bool supress_errors = false;
23
24void
25error_push(Error error) {
26 if (errors_n < ERR_MAX_NUMBER) {
27 errors[errors_n++] = error;
28 }
29}
diff --git a/src/treewalk/errors.h b/src/treewalk/errors.h
deleted file mode 100644
index 7916f4a..0000000
--- a/src/treewalk/errors.h
+++ /dev/null
@@ -1,38 +0,0 @@
1#ifndef BDL_ERRORS_H
2#define BDL_ERRORS_H
3
4typedef enum ErrorType {
5 ERR_TYPE_LEXER,
6 ERR_TYPE_PARSER,
7 ERR_TYPE_RUNTIME,
8} ErrorType;
9
10typedef enum ErrorValue {
11 ERR_UNKNOWN = 0,
12 ERR_UNMATCHED_STRING,
13 ERR_UNBALANCED_PAREN,
14 ERR_NOT_IMPLEMENTED,
15 ERR_EOF_REACHED,
16 ERR_UNKNOWN_TOKEN,
17 ERR_UNKNOWN_OBJ_TYPE,
18 ERR_NOT_A_SYMBOL,
19 ERR_SYMBOL_NOT_FOUND,
20 ERR_OBJ_NOT_CALLABLE,
21 ERR_NOT_ENOUGH_ARGS,
22 ERR_TOO_MANY_ARGS,
23 ERR_WRONG_ARG_TYPE,
24 ERR_DIVISION_BY_ZERO,
25} ErrorValue;
26
27typedef struct Error {
28 ErrorType type;
29 ErrorValue value;
30 size_t line;
31 size_t col;
32} Error;
33
34void error_push(Error error);
35
36#define ERR_MAX_NUMBER 16
37
38#endif // BDL_ERRORS_H
diff --git a/src/treewalk/gc.c b/src/treewalk/gc.c
deleted file mode 100644
index 358a07e..0000000
--- a/src/treewalk/gc.c
+++ /dev/null
@@ -1,199 +0,0 @@
1#include "gc.h"
2
3Environment *
4alloc_env(void) {
5 if (array_size(gc.free_envs.offsets) == 0) {
6 mark_and_sweep();
7 if (array_size(gc.free_envs.offsets) == 0) {
8 fprintf(stderr, "NO MORE ENV MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n");
9 dump_gc();
10 exit(EXIT_FAILURE);
11 // TODO: grow heap tables.
12 }
13 }
14 size_t slot = gc.free_envs.offsets[gc.free_envs.position++];
15 array_head(gc.free_envs.offsets)->size--;
16 return &gc.envs[slot];
17}
18
19void
20push_root(Object *obj) {
21 array_push(gc.roots, obj);
22}
23
24Object *
25pop_root(void) {
26 return array_pop(gc.roots);
27}
28
29void
30push_active_env(Environment *env) {
31 array_push(gc.active_envs, env);
32}
33
34Environment *
35pop_active_env(void) {
36 return array_pop(gc.active_envs);
37}
38
39void
40gc_init(void) {
41 gc = (GC){0};
42
43 array_init(gc.objects, GC_OBJS_CAP);
44 array_init(gc.roots, GC_ROOTS_CAP);
45 array_init(gc.active_envs, GC_ACTIVE_ENVS_CAP);
46 array_init(gc.envs, GC_ENVS_CAP);
47 array_init(gc.free_objects.offsets, GC_OBJS_CAP);
48 array_init(gc.free_envs.offsets, GC_ENVS_CAP);
49
50 // The free list stores the offset from the initial position for all
51 // available slots.
52 for (size_t i = 0; i < GC_OBJS_CAP; i++) {
53 array_push(gc.free_objects.offsets, i);
54 }
55 for (size_t i = 0; i < GC_ENVS_CAP; i++) {
56 array_push(gc.free_envs.offsets, i);
57 }
58}
59
60void
61mark_environment(Environment *env) {
62 if (env == NULL || env->marked) {
63 return;
64 }
65 env->marked = true;
66 HashTablePair *pairs = env->table->pairs;
67 for (size_t i = 0; i < array_cap(pairs); i++) {
68 if (pairs[i].key != NULL) {
69 mark_obj(pairs[i].key);
70 mark_obj(pairs[i].value);
71 }
72 }
73}
74
75void
76mark_obj(Object *obj) {
77 if (obj->marked) {
78 return;
79 }
80 obj->marked = true;
81 if (obj->type == OBJ_TYPE_PAIR) {
82 mark_obj(obj->car);
83 mark_obj(obj->cdr);
84 }
85 if (obj->type == OBJ_TYPE_LAMBDA) {
86 mark_obj(obj->params);
87 mark_obj(obj->body);
88 mark_environment(obj->env);
89 }
90}
91
92void
93mark_and_sweep(void) {
94 // Mark.
95 for (size_t i = 0; i < array_size(gc.active_envs); i++) {
96 mark_environment(gc.active_envs[i]);
97 }
98 for (size_t i = 0; i < array_size(gc.roots); i++) {
99 mark_obj(gc.roots[i]);
100 }
101
102 // Reset the free list.
103 gc.free_objects.position = 0;
104 array_head(gc.free_objects.offsets)->size = 0;
105 gc.free_envs.position = 0;
106 array_head(gc.free_envs.offsets)->size = 0;
107
108 // Sweep.
109 for (size_t i = 0; i < array_cap(gc.objects); i++) {
110 Object *obj = &gc.objects[i];
111 if (!obj->marked) {
112 // Free heap allocated memory for this object if needed.
113 if (obj->type == OBJ_TYPE_SYMBOL) {
114 array_free(obj->symbol);
115 } else if (obj->type == OBJ_TYPE_STRING) {
116 array_free(obj->string);
117 }
118 gc.free_objects.offsets[array_head(gc.free_objects.offsets)->size++] = i;
119 }
120 obj->marked = false;
121 }
122 for (size_t i = 0; i < array_cap(gc.envs); i++) {
123 Environment *env = &gc.envs[i];
124 if (!env->marked) {
125 ht_free(env->table);
126 gc.free_envs.offsets[array_head(gc.free_envs.offsets)->size++] = i;
127 }
128 env->marked = false;
129 }
130}
131
132void
133dump_gc(void) {
134 printf("-------------- ROOTS -------------- \n");
135 for (size_t i = 0; i < array_size(gc.roots); i++) {
136 display(gc.roots[i]);
137 printf("\n");
138 }
139 printf("--------- OBJECTS (TOP 20) -------- \n");
140 for (size_t i = 0; i < 20; i++) {
141 printf("i: %ld -> ", i);
142 Object *obj = &gc.objects[i];
143 display(obj);
144 bool is_free = false;
145 for (size_t j = 0; j < array_cap(gc.objects); j++) {
146 if (gc.free_objects.offsets[j] == i) {
147 is_free = true;
148 break;
149 }
150 }
151 if (is_free) {
152 printf(" [FREE]");
153 }
154 printf("\n");
155 }
156 printf("-------------- MISC --------------- \n");
157 printf("gc.roots.size: %ld\n", array_size(gc.roots));
158 printf("gc.roots.cap: %ld\n", array_size(gc.roots));
159 printf("gc.active_envs.size: %ld\n", array_size(gc.active_envs));
160 printf("gc.active_envs.cap: %ld\n", array_cap(gc.active_envs));
161 printf("gc.obj_cap: %ld\n", array_cap(gc.objects));
162 printf("gc.free_objects.size: %ld\n", array_size(gc.free_objects.offsets));
163 printf("gc.free_objects.cap: %ld\n", array_cap(gc.free_objects.offsets));
164 printf("gc.free_objects.position: %ld\n", gc.free_objects.position);
165 printf("array_size(gc.free_envs.offsets): %ld\n", array_size(gc.free_envs.offsets));
166 printf("gc.free_envs.cap: %ld\n", array_cap(gc.free_envs.offsets));
167 printf("gc.free_envs.position: %ld\n", gc.free_envs.position);
168 printf("gc.envs.size: %ld\n", array_size(gc.envs));
169 printf("gc.envs.cap: %ld\n", array_cap(gc.envs));
170}
171
172Object *
173alloc_object(ObjectType type) {
174 if (array_head(gc.free_objects.offsets)->size == 0) {
175 mark_and_sweep();
176 if (array_head(gc.free_objects.offsets)->size == 0) {
177 fprintf(stderr, "NO MORE OBJ MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n");
178 dump_gc();
179 exit(EXIT_FAILURE);
180 // TODO: grow heap tables.
181 // NOTE: When growing the tables, we WILL lose the pointer
182 // references! Should we work with offsets all the way? That is for
183 // cdr and car? Should we have a utility function? All in all, we
184 // need to refactor the codebase first to work with pointer offsets
185 // rather than objects. This issue is very important, if we are in
186 // the middle of an operation that tries to allocate memory but we
187 // had saved pointers to some object, the pointer references may be
188 // invalidated, crashing or worse, silently returning garbage! Let's
189 // move on for now implementing the GC and we will revisit this part
190 // later.
191 }
192 }
193 size_t slot = gc.free_objects.offsets[gc.free_objects.position++];
194 array_head(gc.free_objects.offsets)->size--;
195 Object *obj = &gc.objects[slot];
196 obj->type = type;
197 obj->marked = false;
198 return obj;
199}
diff --git a/src/treewalk/gc.h b/src/treewalk/gc.h
deleted file mode 100644
index 9ad1615..0000000
--- a/src/treewalk/gc.h
+++ /dev/null
@@ -1,46 +0,0 @@
1#ifndef BDL_GC_H
2#define BDL_GC_H
3
4#include "objects.h"
5#include "environment.h"
6
7typedef struct FreeList {
8 size_t *offsets;
9 size_t position;
10} FreeList;
11
12typedef struct GC {
13 Object **roots;
14 Environment *envs;
15 Object *objects;
16 FreeList free_objects;
17 FreeList free_envs;
18 Environment **active_envs;
19} GC;
20
21void gc_init(void);
22
23// Allocation functions for objects and environments.
24Object * alloc_object(ObjectType type);
25Environment * alloc_env(void);
26
27// Root and environment protector functions.
28void push_root(Object *obj);
29Object * pop_root(void);
30void push_active_env(Environment *env);
31Environment * pop_active_env(void);
32
33// Mark and sweep algorithm functions.
34void mark_environment(Environment *env);
35void mark_obj(Object *obj);
36void mark_and_sweep(void);
37
38// Debugging function to print out the contentes of some GC fields.
39void dump_gc(void);
40
41#define GC_OBJS_CAP 1024 * 1024
42#define GC_ROOTS_CAP 1024
43#define GC_ACTIVE_ENVS_CAP 2
44#define GC_ENVS_CAP 1024 * 4
45
46#endif // BDL_GC_H
diff --git a/src/treewalk/hashtable.h b/src/treewalk/hashtable.h
deleted file mode 100644
index 8f210e3..0000000
--- a/src/treewalk/hashtable.h
+++ /dev/null
@@ -1,191 +0,0 @@
1#ifndef BDL_HASHTABLE_H
2#define BDL_HASHTABLE_H
3
4#include "darray.h"
5#include "objects.h"
6
7// Minimum table capacity.
8#define HT_MIN_CAP 4
9#define HT_MIN_SHIFT 2
10
11// Adjust the load factor threshold at which the table will grow on insertion.
12#define HT_LOAD_THRESHOLD 0.8
13
14typedef struct HashTablePair {
15 Object *key;
16 Object *value;
17} HashTablePair;
18
19typedef struct HashTable {
20 // All available key-value pairs as a dynamic array.
21 HashTablePair *pairs;
22
23 // This table expects the number of buckets to grow in powers of two. To
24 // speedup the default hashing, we memoize the number of bits equivalent to
25 // that power of 2:
26 //
27 // cap := 1024 = 2 ^ 10, shift_amount := 10
28 //
29 uint8_t shift_amount;
30} HashTable;
31
32// Hash a byte stream using a circular shift + XOR hash function.
33static inline uint64_t
34_xor_shift_hash(const char *key, size_t n) {
35 uint64_t hash = 0x65d9d65f6a19574f;
36 char *last = (char *)key + n;
37 while (key != last) {
38 hash ^= (uint64_t)*key++;
39 hash = (hash << 8) | (hash >> (64 - 8));
40 }
41 return hash;
42}
43
44// Use Fibonacci hashing to map a hash to a value in range of the table.
45static inline uint64_t
46_fibonacci_hash(uint64_t hash, size_t shift_amount) {
47 return (hash * UINT64_C(11400714819323198485)) >> (64 - shift_amount);
48}
49
50uint64_t
51ht_hash(const HashTable *table, const Object *key) {
52 uint64_t hash = 0;
53 switch (key->type) {
54 case OBJ_TYPE_FIXNUM: {
55 hash = key->fixnum;
56 } break;
57 case OBJ_TYPE_STRING: {
58 hash = _xor_shift_hash(key->string, array_size(key->string));
59 } break;
60 case OBJ_TYPE_SYMBOL: {
61 hash = _xor_shift_hash(key->symbol, array_size(key->symbol));
62 } break;
63 case OBJ_TYPE_BOOL:
64 case OBJ_TYPE_NIL:
65 case OBJ_TYPE_PAIR:
66 case OBJ_TYPE_LAMBDA:
67 case OBJ_TYPE_PROCEDURE:
68 case OBJ_TYPE_ERR: {
69 hash = (uintptr_t)key;
70 } break;
71 }
72 hash = _fibonacci_hash(hash, table->shift_amount);
73 return hash;
74}
75
76static inline float
77ht_load_factor(const HashTable *table) {
78 return (float)array_size(table->pairs) / (float)array_cap(table->pairs);
79}
80
81HashTable *
82ht_init(void) {
83 HashTable *table = malloc(sizeof(HashTable));
84 table->pairs = NULL;
85 array_init(table->pairs, HT_MIN_CAP);
86 for (size_t i = 0; i < array_cap(table->pairs); i++) {
87 table->pairs[i] = (HashTablePair){NULL, NULL};
88 }
89 table->shift_amount = HT_MIN_SHIFT;
90 return table;
91}
92
93void
94_ht_insert(HashTable *table, const Object *key, const Object *value) {
95 size_t position = ht_hash(table, key);
96 size_t probe_position = position;
97
98 // Verify the key in that position is free. If not, use linear probing to
99 // find the next free slot.
100 HashTablePair *pairs = table->pairs;
101 while (true) {
102 if (pairs[probe_position].key == NULL) {
103 array_head(pairs)->size++;
104 break;
105 }
106 if (obj_eq(pairs[probe_position].key, key)) {
107 break;
108 }
109 if (probe_position == array_cap(pairs) - 1) {
110 probe_position = 0;
111 } else {
112 probe_position++;
113 }
114 }
115 pairs[probe_position].key = (Object *)key;
116 pairs[probe_position].value = (Object *)value;
117}
118
119void
120_ht_maybe_grow(HashTable *table) {
121 HashTablePair *pairs = table->pairs;
122 if (ht_load_factor(table) < HT_LOAD_THRESHOLD) {
123 return;
124 }
125
126 // Create a new array with 2x capacity.
127 table->pairs = NULL;
128 array_init(table->pairs, array_cap(pairs) * 2);
129 for (size_t i = 0; i < array_cap(table->pairs); i++) {
130 table->pairs[i] = (HashTablePair){NULL, NULL};
131 }
132 table->shift_amount++;
133
134 // Hash everything in the table for the new array capacity.
135 for (size_t i = 0; i < array_cap(pairs); i++) {
136 if (pairs[i].key != NULL) {
137 _ht_insert(table, pairs[i].key, pairs[i].value);
138 }
139 }
140
141 // Free the old array.
142 array_free(pairs);
143}
144
145void
146ht_insert(HashTable *table, const Object *key, const Object *value) {
147 _ht_maybe_grow(table);
148 _ht_insert(table, key, value);
149 return;
150}
151
152Object *
153ht_lookup(const HashTable *table, const Object *key) {
154 size_t position = ht_hash(table, key);
155 size_t probe_position = position;
156
157 // Verify the key in that position is the same. If not perform linear
158 // probing to find it.
159 HashTablePair *pairs = table->pairs;
160 while (true) {
161 if (pairs[probe_position].key == NULL) {
162 return NULL;
163 }
164 if (obj_eq(pairs[probe_position].key, key)) {
165 break;
166 }
167 if (probe_position == array_cap(pairs) - 1) {
168 probe_position = 0;
169 } else {
170 probe_position++;
171 }
172 if (probe_position == position) {
173 return NULL;
174 }
175 }
176 return pairs[probe_position].value;
177}
178
179void
180ht_free(HashTable *table) {
181 if (table == NULL) {
182 return;
183 }
184 if (table->pairs == NULL) {
185 return;
186 }
187 array_free(table->pairs);
188 free(table);
189}
190
191#endif // BDL_HASHTABLE_H
diff --git a/src/treewalk/lexer.c b/src/treewalk/lexer.c
deleted file mode 100644
index 38ca37c..0000000
--- a/src/treewalk/lexer.c
+++ /dev/null
@@ -1,257 +0,0 @@
1#include "lexer.h"
2
3void
4print_token(Token tok) {
5 printf("LINE: %3ld COL: %3ld ", tok.line, tok.column);
6 switch (tok.type) {
7 case TOKEN_LPAREN: {
8 printf("TOKEN_LPAREN");
9 } break;
10 case TOKEN_RPAREN: {
11 printf("TOKEN_RPAREN");
12 } break;
13 case TOKEN_QUOTE: {
14 printf("TOKEN_QUOTE");
15 } break;
16 case TOKEN_TRUE: {
17 printf("TOKEN_TRUE");
18 } break;
19 case TOKEN_FALSE: {
20 printf("TOKEN_FALSE");
21 } break;
22 case TOKEN_NIL: {
23 printf("TOKEN_NIL");
24 } break;
25 case TOKEN_FIXNUM: {
26 printf("TOKEN_FIXNUM -> ");
27 sv_write(&tok.value, stdout);
28 } break;
29 case TOKEN_SYMBOL: {
30 printf("TOKEN_SYMBOL -> ");
31 sv_write(&tok.value, stdout);
32 } break;
33 case TOKEN_STRING: {
34 printf("TOKEN_STRING -> ");
35 sv_write(&tok.value, stdout);
36 } break;
37 case TOKEN_EOF: {
38 printf("TOKEN_EOF");
39 } break;
40 case TOKEN_UNKNOWN: {
41 printf("TOKEN_UNKNOWN");
42 } break;
43 }
44 printf("\n");
45}
46
47char
48scan_next(Scanner *scanner) {
49 char c = sv_next(&scanner->current);
50 if (c == '\n') {
51 scanner->line_number++;
52 scanner->col_number = 1;
53 } else {
54 scanner->col_number++;
55 }
56 scanner->offset++;
57 return c;
58}
59
60char
61scan_peek(const Scanner *scanner) {
62 return sv_peek(&scanner->current);
63}
64
65bool
66scan_has_next(const Scanner *scanner) {
67 return scanner->current.n != 0;
68}
69
70void
71skip_whitespace(Scanner *scanner) {
72 while (scan_has_next(scanner)) {
73 char c = scan_peek(scanner);
74 switch (c) {
75 case ' ':
76 case '\f':
77 case '\n':
78 case '\r':
79 case '\t':
80 case '\v': {
81 scan_next(scanner);
82 } break;
83 default: {
84 return;
85 } break;
86 }
87 }
88}
89
90bool
91is_delimiter(char c) {
92 switch (c) {
93 case EOF:
94 case '\0':
95 case ';':
96 case '"':
97 case '\'':
98 case '(':
99 case ')':
100 case ' ':
101 case '\f':
102 case '\n':
103 case '\r':
104 case '\t':
105 case '\v': {
106 return true;
107 } break;
108 }
109 return false;
110}
111
112TokenType
113find_primitive_type(const StringView value) {
114 bool is_fixnum = true;
115 for (size_t i = 0; i < value.n; i++) {
116 char c = value.start[i];
117 if (i == 0 && c == '-' && value.n > 1) {
118 continue;
119 }
120 if (!(c >= '0' && c <= '9')) {
121 is_fixnum = false;
122 break;
123 }
124 }
125 if (is_fixnum) {
126 return TOKEN_FIXNUM;
127 }
128 if (sv_equal(&value, &(StringView){"true", 4})) {
129 return TOKEN_TRUE;
130 }
131 if (sv_equal(&value, &(StringView){"false", 5})) {
132 return TOKEN_FALSE;
133 }
134 return TOKEN_SYMBOL;
135}
136
137Token *
138tokenize(const StringView *sv) {
139 Token *tokens = NULL;
140 array_init(tokens, 1);
141 Scanner scanner = (Scanner){
142 .current = *sv,
143 .line_number = 1,
144 .col_number = 1,
145 };
146
147 while (scan_has_next(&scanner)) {
148 skip_whitespace(&scanner);
149 size_t line = scanner.line_number;
150 size_t col = scanner.col_number;
151 size_t offset = scanner.offset;
152 char c = scan_next(&scanner);
153 switch (c) {
154 case ';': {
155 while ((c = scan_next(&scanner)) != '\n' && c != '\0') {}
156 } break;
157 case '"': {
158 char prev = c;
159 bool found = false;
160 size_t n = 0;
161 while (scan_has_next(&scanner)) {
162 c = scan_next(&scanner);
163 if (c == '"' && prev != '\\') {
164 found = true;
165 break;
166 }
167 prev = c;
168 n++;
169 }
170 if (!found) {
171 error_push((Error){
172 .type = ERR_TYPE_LEXER,
173 .value = ERR_UNMATCHED_STRING,
174 .line = line,
175 .col = col,
176 });
177 return tokens;
178 }
179 Token token = (Token){
180 .value = (StringView){
181 .start = &sv->start[offset + 1],
182 .n = n,
183 },
184 .type = TOKEN_STRING,
185 .line = line,
186 .column = col,
187 };
188 array_push(tokens, token);
189 } break;
190 case '\'': {
191 Token token = (Token){
192 .type = TOKEN_QUOTE,
193 .line = line,
194 .column = col,
195 };
196 array_push(tokens, token);
197 } break;
198 case '(': {
199 if (scan_peek(&scanner) == ')') {
200 scan_next(&scanner);
201 Token token = (Token){
202 .type = TOKEN_NIL,
203 .line = line,
204 .column = col,
205 };
206 array_push(tokens, token);
207 } else {
208 Token token = (Token){
209 .type = TOKEN_LPAREN,
210 .line = line,
211 .column = col,
212 };
213 array_push(tokens, token);
214 }
215 } break;
216 case ')': {
217 Token token = (Token){
218 .type = TOKEN_RPAREN,
219 .line = line,
220 .column = col,
221 };
222 array_push(tokens, token);
223 } break;
224 default: {
225 size_t n = 1;
226 while (!is_delimiter(scan_peek(&scanner))) {
227 scan_next(&scanner);
228 n++;
229 }
230 if (c == EOF || c == '\0') {
231 break;
232 }
233 Token token = (Token){
234 .value = (StringView){
235 .start = &sv->start[offset],
236 .n = n,
237 },
238 .type = TOKEN_SYMBOL,
239 .line = line,
240 .column = col,
241 };
242 token.type = find_primitive_type(token.value);
243 array_push(tokens, token);
244 } break;
245 }
246 }
247
248 // Push EOF token.
249 Token token = (Token){
250 .type = TOKEN_EOF,
251 .line = scanner.line_number,
252 .column = 1,
253 };
254 array_push(tokens, token);
255
256 return tokens;
257}
diff --git a/src/treewalk/lexer.h b/src/treewalk/lexer.h
deleted file mode 100644
index 2b2789f..0000000
--- a/src/treewalk/lexer.h
+++ /dev/null
@@ -1,57 +0,0 @@
1#ifndef BDL_LEXER_H
2#define BDL_LEXER_H
3
4typedef enum TokenType {
5 TOKEN_UNKNOWN = 0,
6 TOKEN_LPAREN,
7 TOKEN_RPAREN,
8 TOKEN_QUOTE,
9 TOKEN_TRUE,
10 TOKEN_FALSE,
11 TOKEN_NIL,
12 TOKEN_FIXNUM,
13 TOKEN_SYMBOL,
14 TOKEN_STRING,
15 TOKEN_EOF,
16} TokenType;
17
18typedef struct Token {
19 TokenType type;
20 StringView value;
21 size_t line;
22 size_t column;
23} Token;
24
25typedef struct Scanner {
26 StringView current;
27 size_t line_number;
28 size_t col_number;
29 size_t offset;
30} Scanner;
31
32// Print a token to standard output for debugging purposes.
33void print_token(Token tok);
34
35// Same functionality as the ScanView pairs, but keeping track of line and
36// column numbers.
37char scan_next(Scanner *scanner);
38char scan_peek(const Scanner *scanner);
39
40// Check if the current scanner still have characters left.
41bool scan_has_next(const Scanner *scanner);
42
43// Advance the scanner until we ran out of whitespace.
44void skip_whitespace(Scanner *scanner);
45
46// Check if a given character is a delimiter.
47bool is_delimiter(char c);
48
49// Extract the token type from the current string.
50TokenType find_primitive_type(const StringView value);
51
52// Generate a list of tokens from the given string.
53Token * tokenize(const StringView *sv);
54
55#define TOK_BUF_CAP 256
56
57#endif // BDL_LEXER_H
diff --git a/src/treewalk/main.c b/src/treewalk/main.c
deleted file mode 100755
index a5888fd..0000000
--- a/src/treewalk/main.c
+++ /dev/null
@@ -1,288 +0,0 @@
1#include <assert.h>
2#include <getopt.h>
3#include <stdbool.h>
4#include <stdint.h>
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
8
9#include "darray.h"
10#include "hashtable.h"
11
12#include "singletons.c"
13
14#include "environment.c"
15#include "errors.c"
16#include "gc.c"
17#include "lexer.c"
18#include "objects.c"
19#include "parser.c"
20#include "primitives.c"
21#include "read_line.c"
22#include "string_view.c"
23
24void
25init(void) {
26 // Initialize garbage collector.
27 gc_init();
28
29 // Initialize singletons.
30 obj_nil = alloc_object(OBJ_TYPE_NIL);
31 obj_true = alloc_object(OBJ_TYPE_BOOL);
32 obj_false = alloc_object(OBJ_TYPE_BOOL);
33 obj_err = alloc_object(OBJ_TYPE_ERR);
34 obj_quote = make_symbol((StringView){"quote", 5});
35 proc_if = alloc_object(OBJ_TYPE_ERR);
36 push_root(obj_nil);
37 push_root(obj_true);
38 push_root(obj_false);
39 push_root(obj_err);
40 push_root(obj_quote);
41 push_root(proc_if);
42
43 // Global environment.
44 global_env = env_create(NULL);
45 // TODO: make sure we create symbols and strings only once (interning
46 // strings?)
47 push_active_env(global_env);
48
49 // Primitive symbols.
50 MAKE_ENV_VAR(global_env, "else", obj_true);
51 MAKE_ENV_VAR(global_env, "nil", obj_nil);
52 MAKE_ENV_VAR(global_env, "if", proc_if);
53
54 // Primitive procedures.
55 MAKE_ENV_PROC(global_env, "eval", proc_eval);
56 MAKE_ENV_PROC(global_env, "quote", proc_quote);
57 MAKE_ENV_PROC(global_env, "car", proc_car);
58 MAKE_ENV_PROC(global_env, "cdr", proc_cdr);
59 MAKE_ENV_PROC(global_env, "cons", proc_cons);
60 MAKE_ENV_PROC(global_env, "list", proc_list);
61 MAKE_ENV_PROC(global_env, "+", proc_sum);
62 MAKE_ENV_PROC(global_env, "-", proc_sub);
63 MAKE_ENV_PROC(global_env, "*", proc_mul);
64 MAKE_ENV_PROC(global_env, "/", proc_div);
65 MAKE_ENV_PROC(global_env, "%", proc_mod);
66 MAKE_ENV_PROC(global_env, "print", proc_print);
67 MAKE_ENV_PROC(global_env, "display", proc_display);
68 MAKE_ENV_PROC(global_env, "newline", proc_newline);
69 MAKE_ENV_PROC(global_env, "boolean?", proc_is_boolean);
70 MAKE_ENV_PROC(global_env, "nil?", proc_is_nil);
71 MAKE_ENV_PROC(global_env, "symbol?", proc_is_symbol);
72 MAKE_ENV_PROC(global_env, "string?", proc_is_string);
73 MAKE_ENV_PROC(global_env, "fixnum?", proc_is_fixnum);
74 MAKE_ENV_PROC(global_env, "pair?", proc_is_pair);
75 MAKE_ENV_PROC(global_env, "procedure?", proc_is_procedure);
76 MAKE_ENV_PROC(global_env, "error?", proc_is_error);
77 MAKE_ENV_PROC(global_env, "not", proc_not);
78 MAKE_ENV_PROC(global_env, "and", proc_and);
79 MAKE_ENV_PROC(global_env, "or", proc_or);
80 MAKE_ENV_PROC(global_env, "cond", proc_cond);
81 MAKE_ENV_PROC(global_env, "<", proc_num_less_than);
82 MAKE_ENV_PROC(global_env, "<=", proc_num_lesseq_than);
83 MAKE_ENV_PROC(global_env, ">", proc_num_greater_than);
84 MAKE_ENV_PROC(global_env, ">=", proc_num_greatereq_than);
85 MAKE_ENV_PROC(global_env, "=", proc_num_equal);
86 MAKE_ENV_PROC(global_env, "eq?", proc_equal);
87 MAKE_ENV_PROC(global_env, "def", proc_define);
88 MAKE_ENV_PROC(global_env, "set!", proc_set);
89 MAKE_ENV_PROC(global_env, "lambda", proc_lambda);
90 MAKE_ENV_PROC(global_env, "fun", proc_fun);
91
92 // Runtime procedures.
93 MAKE_ENV_PROC(global_env, "supress-errors", proc_supress_errors);
94}
95
96void
97process_source(const StringView *source) {
98 Token *tokens = tokenize(source);
99 if (errors_n != 0) {
100 if (tokens != NULL) {
101 array_free(tokens);
102 }
103 return;
104 }
105
106 Visitor visitor = (Visitor){
107 .tokens = tokens,
108 .current = 0,
109 };
110 while (has_next_token(&visitor) && peek_token(&visitor).type != TOKEN_EOF) {
111 // Check the root node stack size before parsing
112 size_t root_stack_size = array_size(gc.roots);
113 Object *root = parse_tree(&visitor);
114 array_head(gc.roots)->size = root_stack_size;
115 if (root == obj_err || errors_n != 0) {
116 break;
117 }
118 push_root(root);
119
120 Object *result = eval(global_env, root);
121 if (result != obj_nil) {
122 display(result);
123 printf("\n");
124 }
125 pop_root();
126 }
127
128 if (tokens != NULL) {
129 array_free(tokens);
130 }
131}
132
133#define REPL_PROMPT "bdl> "
134
135void
136run_repl(void) {
137 printf("BDL REPL (Press Ctrl-D or Ctrl-C to exit)\n");
138 while (true) {
139 printf(REPL_PROMPT);
140 StringView sv = read_line();
141 if (sv.start == NULL) {
142 return;
143 }
144 process_source(&sv);
145
146 // Check if there were any errors.
147 if (errors_n != 0 && !supress_errors) {
148 for (size_t i = 0; i < errors_n; i++) {
149 Error err = errors[i];
150 for (size_t j = 0; j < err.col + sizeof(REPL_PROMPT) - 2; j++) {
151 putchar(' ');
152 }
153 printf("|\n");
154 for (size_t j = 0; j < err.col + sizeof(REPL_PROMPT) - 2; j++) {
155 putchar(' ');
156 }
157 printf("%s\n", error_msgs[err.value]);
158 }
159 errors_n = 0;
160 continue;
161 }
162 }
163}
164
165void
166run_file(char *file_name) {
167 FILE *file = fopen(file_name, "r");
168 if (!file) {
169 fprintf(stderr, "error: couldn't open input file: %s\n", file_name);
170 exit(EXIT_FAILURE);
171 }
172
173 // Read entire file into memory.
174 fseek(file, 0, SEEK_END);
175 size_t file_size = ftell(file);
176 fseek(file, 0, SEEK_SET);
177
178 char *source = malloc(file_size + 1);
179 fread(source, 1, file_size, file);
180 source[file_size] = 0;
181
182 StringView sv = (StringView){
183 .start = source,
184 .n = file_size,
185 };
186
187 process_source(&sv);
188
189 // Check if there were any errors.
190 if (errors_n != 0 && !supress_errors) {
191 for (size_t i = 0; i < errors_n; i++) {
192 Error err = errors[i];
193 fprintf(stderr, "%s", file_name);
194 if (err.line != 0) {
195 fprintf(stderr, ":%ld:%ld", err.line, err.col);
196 }
197 fprintf(stderr, ": %s\n", error_msgs[err.value]);
198 }
199 errors_n = 0;
200 }
201
202 free(source);
203 fclose(file);
204}
205
206#define STDIN_BUF_CAP 16
207
208void
209run_stdin(void) {
210 size_t buf_size = 0;
211 char *source = NULL;
212 array_init(source, STDIN_BUF_CAP);
213
214 char c;
215 while ((c = getchar()) != EOF) {
216 array_push(source, c);
217 buf_size++;
218 }
219
220 StringView sv = (StringView){
221 .start = source,
222 .n = buf_size,
223 };
224
225 process_source(&sv);
226
227 // Check if there were any errors.
228 if (errors_n != 0 && !supress_errors) {
229 for (size_t i = 0; i < errors_n; i++) {
230 Error err = errors[i];
231 fprintf(stderr, "stdin");
232 if (err.line != 0) {
233 fprintf(stderr, ":%ld:%ld", err.line, err.col);
234 }
235 fprintf(stderr, ": %s\n", error_msgs[err.value]);
236 }
237 errors_n = 0;
238 }
239
240 array_free(source);
241}
242
243#ifndef BIN_NAME
244#define BIN_NAME "bdl"
245#endif
246
247void
248print_usage(void) {
249 printf("Usage: %s [options] <filename filename ...>\n", BIN_NAME);
250 printf("\n");
251 printf("\t-i\tInteractive mode (REPL).\n");
252 printf("\n");
253}
254
255int
256main(int argc, char *argv[]) {
257 init();
258
259 int option;
260 while ((option = getopt(argc, argv, "i")) != -1) {
261 switch (option) {
262 case 'i': {
263 // Interactive mode.
264 run_repl();
265 return EXIT_SUCCESS;
266 } break;
267 default: {
268 print_usage();
269 return EXIT_FAILURE;
270 } break;
271 }
272 }
273
274 // Run from stdin.
275 if (optind == argc) {
276 run_stdin();
277 return EXIT_SUCCESS;
278 }
279
280 // Run from file.
281 while (optind < argc) {
282 char *file_name = argv[optind];
283 run_file(file_name);
284 optind++;
285 }
286
287 return EXIT_SUCCESS;
288}
diff --git a/src/treewalk/objects.c b/src/treewalk/objects.c
deleted file mode 100644
index c71bc40..0000000
--- a/src/treewalk/objects.c
+++ /dev/null
@@ -1,141 +0,0 @@
1#include "gc.h"
2#include "objects.h"
3
4//
5// Constructors.
6//
7
8Object *
9make_fixnum(ssize_t num) {
10 Object *obj = alloc_object(OBJ_TYPE_FIXNUM);
11 obj->fixnum = num;
12 return obj;
13}
14
15Object *
16make_procedure(Object *(*proc)(struct Environment *, struct Object *args)) {
17 Object *obj = alloc_object(OBJ_TYPE_PROCEDURE);
18 obj->proc = proc;
19 return obj;
20}
21
22Object *
23make_pair(Object *car, Object *cdr) {
24 Object *obj = alloc_object(OBJ_TYPE_PAIR);
25 obj->car = car;
26 obj->cdr = cdr;
27 return obj;
28}
29
30Object *
31make_symbol(StringView sv) {
32 Object *obj = alloc_object(OBJ_TYPE_SYMBOL);
33 obj->symbol = NULL;
34 array_init(obj->symbol, sv.n);
35 array_insert(obj->symbol, sv.start, sv.n);
36 return obj;
37}
38
39Object *
40make_string(void) {
41 Object *obj = alloc_object(OBJ_TYPE_STRING);
42 obj->string = NULL;
43 array_init(obj->string, 0);
44 return obj;
45}
46
47void
48append_string(Object *obj, const StringView sv) {
49 if (sv.n == 0) {
50 return;
51 }
52 array_insert(obj->string, sv.start, sv.n);
53}
54
55void
56display_pair(Object *root) {
57 display(root->car);
58 if (root->cdr->type == OBJ_TYPE_PAIR) {
59 printf(" ");
60 display_pair(root->cdr);
61 } else if (root->cdr == obj_nil) {
62 return;
63 } else {
64 printf(" . ");
65 display(root->cdr);
66 }
67}
68
69void
70display(Object *root) {
71 switch (root->type) {
72 case OBJ_TYPE_FIXNUM: {
73 printf("%zd", root->fixnum);
74 } break;
75 case OBJ_TYPE_BOOL: {
76 if (root == obj_true) {
77 printf("true");
78 } else {
79 printf("false");
80 }
81 } break;
82 case OBJ_TYPE_NIL: {
83 printf("()");
84 } break;
85 case OBJ_TYPE_STRING: {
86 printf("\"%.*s\"", (int)array_size(root->string), root->string);
87 } break;
88 case OBJ_TYPE_SYMBOL: {
89 printf(":%.*s", (int)array_size(root->symbol), root->symbol);
90 } break;
91 case OBJ_TYPE_PAIR: {
92 printf("(");
93 display_pair(root);
94 printf(")");
95 } break;
96 case OBJ_TYPE_LAMBDA:
97 case OBJ_TYPE_PROCEDURE: {
98 printf("#{procedure}");
99 } break;
100 case OBJ_TYPE_ERR: {
101 printf("#{error}");
102 } break;
103 }
104 return;
105}
106
107bool
108obj_eq(const Object *a, const Object* b) {
109 if (a->type != b->type) {
110 return false;
111 }
112 switch (a->type) {
113 case OBJ_TYPE_FIXNUM: {
114 return a->fixnum == b->fixnum;
115 } break;
116 case OBJ_TYPE_STRING: {
117 if (array_size(a->string) != array_size(b->string)) {
118 return false;
119 }
120 for (size_t i = 0; i < array_size(a->string); i++) {
121 if (a->string[i] != b->string[i]) {
122 return false;
123 }
124 }
125 } break;
126 case OBJ_TYPE_SYMBOL: {
127 if (array_size(a->symbol) != array_size(b->symbol)) {
128 return false;
129 }
130 for (size_t i = 0; i < array_size(a->symbol); i++) {
131 if (a->symbol[i] != b->symbol[i]) {
132 return false;
133 }
134 }
135 } break;
136 default: {
137 return a == b;
138 } break;
139 }
140 return true;
141}
diff --git a/src/treewalk/objects.h b/src/treewalk/objects.h
deleted file mode 100644
index ed623eb..0000000
--- a/src/treewalk/objects.h
+++ /dev/null
@@ -1,75 +0,0 @@
1#ifndef BDL_OBJECTS_H
2#define BDL_OBJECTS_H
3
4#include "string_view.h"
5
6typedef enum ObjectType {
7 OBJ_TYPE_FIXNUM,
8 OBJ_TYPE_BOOL,
9 OBJ_TYPE_NIL,
10 OBJ_TYPE_SYMBOL,
11 OBJ_TYPE_STRING,
12 OBJ_TYPE_PAIR,
13 OBJ_TYPE_PROCEDURE,
14 OBJ_TYPE_LAMBDA,
15 OBJ_TYPE_ERR,
16} ObjectType;
17
18struct Environment;
19
20typedef struct Object {
21 ObjectType type;
22 bool marked;
23 union {
24 // OBJ_TYPE_FIXNUM
25 ssize_t fixnum;
26
27 // OBJ_TYPE_STRING
28 struct {
29 char *string;
30 };
31
32 // OBJ_TYPE_PAIR
33 struct {
34 struct Object *car;
35 struct Object *cdr;
36 };
37
38 // OBJ_TYPE_SYMBOL
39 struct {
40 char *symbol;
41 };
42
43 // OBJ_TYPE_PROCEDURE
44 struct Object *(*proc)(struct Environment *env, struct Object *args);
45
46 // OBJ_TYPE_LAMBDA
47 struct {
48 struct Object *params;
49 struct Object *body;
50 struct Environment *env;
51 };
52 };
53} Object;
54
55// Object constructors.
56Object * make_fixnum(ssize_t num);
57Object * make_procedure(Object *(*proc)(struct Environment *, Object *args));
58Object * make_pair(Object *car, Object *cdr);
59Object * make_symbol(StringView sv);
60Object * make_string(void);
61void append_string(Object *obj, const StringView sv);
62
63// Object representation.
64void display(Object *root);
65void display_pair(Object *root);
66
67// Object comparison.
68bool obj_eq(const Object *a, const Object* b);
69
70// Utility macros.
71#define DEBUG_OBJ(MSG,OBJ) printf((MSG)); display(OBJ); printf("\n");
72#define PRINT_OBJ(OBJ) display(OBJ); printf("\n");
73#define MAKE_SYM(STR) make_symbol((StringView){(STR), sizeof(STR) - 1})
74
75#endif // BDL_OBJECTS_H
diff --git a/src/treewalk/parser.c b/src/treewalk/parser.c
deleted file mode 100644
index a2f0f71..0000000
--- a/src/treewalk/parser.c
+++ /dev/null
@@ -1,139 +0,0 @@
1#include "parser.h"
2
3Token
4peek_token(const Visitor *visitor) {
5 return visitor->tokens[visitor->current];
6}
7
8Token
9next_token(Visitor *visitor) {
10 return visitor->tokens[visitor->current++];
11}
12
13bool
14has_next_token(const Visitor *visitor) {
15 return visitor->current < array_size(visitor->tokens);
16}
17
18Object *
19parse_fixnum(Token tok) {
20 ssize_t num = 0;
21 int sign = 1;
22 for (size_t i = 0; i < tok.value.n; i++) {
23 char c = tok.value.start[i];
24 if (c == '-') {
25 sign = -1;
26 continue;
27 }
28 num = num * 10 + (c - '0');
29 }
30
31 Object *obj = make_fixnum(num * sign);
32 push_root(obj);
33 return obj;
34}
35
36Object *
37parse_list(Visitor *vs) {
38 Token tok = peek_token(vs);
39 if (tok.type == TOKEN_EOF) {
40 return obj_err;
41 }
42 Object *root = make_pair(obj_nil, obj_nil);
43 push_root(root);
44 Object *next_obj = parse_tree(vs);
45 if (next_obj == obj_err) {
46 return obj_err;
47 }
48 root->car = next_obj;
49 Object *list = root;
50 while (has_next_token(vs)) {
51 Token tok = peek_token(vs);
52 if (tok.type == TOKEN_RPAREN) {
53 next_token(vs);
54 break;
55 }
56 if (tok.type == TOKEN_EOF) {
57 return obj_err;
58 }
59 next_obj = parse_tree(vs);
60 if (next_obj == obj_err) {
61 return obj_err;
62 }
63 list->cdr = make_pair(next_obj, obj_nil);
64 list = list->cdr;
65 }
66 return root;
67}
68
69Object *
70parse_tree(Visitor *vs) {
71 Token tok = next_token(vs);
72 switch (tok.type) {
73 case TOKEN_FIXNUM: {
74 return parse_fixnum(tok);
75 } break;
76 case TOKEN_TRUE: {
77 return obj_true;
78 } break;
79 case TOKEN_FALSE: {
80 return obj_false;
81 } break;
82 case TOKEN_RPAREN: {
83 error_push((Error){
84 .type = ERR_TYPE_PARSER,
85 .value = ERR_UNBALANCED_PAREN,
86 .line = tok.line,
87 .col = tok.column,
88 });
89 return obj_err;
90 } break;
91 case TOKEN_QUOTE: {
92 Object *base = make_pair(obj_quote, obj_nil);
93 base->cdr = make_pair(obj_nil, obj_nil);
94 push_root(base);
95 Object *next_obj = parse_tree(vs);
96 if (next_obj == obj_err) {
97 return obj_err;
98 }
99 base->cdr->car = next_obj;
100 return base;
101 } break;
102 case TOKEN_LPAREN: {
103 Object *obj = parse_list(vs);
104 if (obj == obj_err) {
105 error_push((Error){
106 .type = ERR_TYPE_PARSER,
107 .value = ERR_UNBALANCED_PAREN,
108 .line = tok.line,
109 .col = tok.column,
110 });
111 }
112 return obj;
113 } break;
114 case TOKEN_STRING: {
115 Object *obj = make_string();
116 push_root(obj);
117 append_string(obj, tok.value);
118 return obj;
119 } break;
120 case TOKEN_SYMBOL: {
121 Object *obj = make_symbol(tok.value);
122 push_root(obj);
123 return obj;
124 } break;
125 case TOKEN_NIL: {
126 return obj_nil;
127 } break;
128 default: {
129 break;
130 } break;
131 }
132 error_push((Error){
133 .type = ERR_TYPE_PARSER,
134 .value = ERR_EOF_REACHED,
135 .line = tok.line,
136 .col = tok.column,
137 });
138 return obj_err;
139}
diff --git a/src/treewalk/parser.h b/src/treewalk/parser.h
deleted file mode 100644
index 3834c75..0000000
--- a/src/treewalk/parser.h
+++ /dev/null
@@ -1,22 +0,0 @@
1#ifndef BDL_PARSER_H
2#define BDL_PARSER_H
3
4typedef struct Visitor {
5 Token *tokens;
6 size_t current;
7} Visitor;
8
9// Mimics the functionality in the Scanner functions, but for entire tokens.
10Token next_token(Visitor *visitor);
11Token peek_token(const Visitor *visitor);
12bool has_next_token(const Visitor *visitor);
13
14// Parse a token into a fixnum object.
15Object * parse_fixnum(Token tok);
16
17// Recursive descent parser. If an object is not a list the parsing is handled
18// by the parse_tree function.
19Object * parse_list(Visitor *vs);
20Object * parse_tree(Visitor *vs);
21
22#endif // BDL_PARSER_H
diff --git a/src/treewalk/primitives.c b/src/treewalk/primitives.c
deleted file mode 100644
index 8b0d407..0000000
--- a/src/treewalk/primitives.c
+++ /dev/null
@@ -1,918 +0,0 @@
1#include "primitives.h"
2
3Object *
4eval(Environment *env, Object *root) {
5 Object* lambda = NULL;
6 Object* args = NULL;
7 Object* ret = NULL;
8 bool recursion_active = false;
9eval_start:
10 switch (root->type) {
11 case OBJ_TYPE_ERR:
12 case OBJ_TYPE_PROCEDURE:
13 case OBJ_TYPE_LAMBDA:
14 case OBJ_TYPE_FIXNUM:
15 case OBJ_TYPE_BOOL:
16 case OBJ_TYPE_NIL:
17 case OBJ_TYPE_STRING: {
18 ret = root;
19 goto eval_success;
20 } break;
21 case OBJ_TYPE_SYMBOL: {
22 Object *val = env_lookup(env, root);
23 if (val == obj_err) {
24 error_push((Error){
25 .type = ERR_TYPE_RUNTIME,
26 .value = ERR_SYMBOL_NOT_FOUND,
27 });
28 return obj_err;
29 }
30 ret = val;
31 goto eval_success;
32 } break;
33 case OBJ_TYPE_PAIR: {
34 if (root->car->type == OBJ_TYPE_SYMBOL) {
35 Object *val = env_lookup(env, root->car);
36 if (val == obj_err) {
37 error_push((Error){
38 .type = ERR_TYPE_RUNTIME,
39 .value = ERR_SYMBOL_NOT_FOUND,
40 });
41 return obj_err;
42 }
43
44 // Primitive `if` procedure with TCO.
45 if (val == proc_if) {
46 Object *obj = root->cdr;
47 if (obj == obj_nil || obj->cdr == obj_nil) {
48 error_push((Error){
49 .type = ERR_TYPE_RUNTIME,
50 .value = ERR_NOT_ENOUGH_ARGS,
51 });
52 return obj_err;
53 }
54 Object *car = obj->car;
55 Object *cdr = obj->cdr;
56 Object *condition = eval(env, car);
57 if (condition == obj_err) {
58 return obj_err;
59 }
60 if (condition == obj_true) {
61 root = cdr->car;
62 } else if (cdr->cdr != obj_nil) {
63 root = cdr->cdr->car;
64 } else {
65 return obj_nil;
66 }
67 goto eval_start;
68 }
69
70 if (val->type == OBJ_TYPE_PROCEDURE) {
71 ret = val->proc(env, root->cdr);
72 goto eval_success;
73 }
74 if (val->type == OBJ_TYPE_LAMBDA) {
75 lambda = val;
76 goto eval_lambda;
77 }
78 error_push((Error){
79 .type = ERR_TYPE_RUNTIME,
80 .value = ERR_OBJ_NOT_CALLABLE,
81 });
82 return obj_err;
83 }
84 lambda = eval(env, root->car);
85 if (lambda == obj_err) {
86 return obj_err;
87 }
88 if (lambda->type != OBJ_TYPE_LAMBDA) {
89 error_push((Error){
90 .type = ERR_TYPE_RUNTIME,
91 .value = ERR_OBJ_NOT_CALLABLE,
92 });
93 return obj_err;
94 }
95
96eval_lambda:
97 args = root->cdr;
98 Object *params = lambda->params;
99 if (!recursion_active) {
100 recursion_active = true;
101 // Protect current stack.
102 Environment *tmp = env_create(lambda->env);
103 push_active_env(tmp);
104 // Extend environment.
105 env = env_extend(tmp, env);
106 }
107
108 // Create temporary environment to store bindings.
109 Environment *tmp = env_create(env);
110 push_active_env(tmp);
111
112 // Evaluate arguments in temporary environment.
113 while (params != obj_nil) {
114 if (args == obj_nil) {
115 error_push((Error){
116 .type = ERR_TYPE_RUNTIME,
117 .value = ERR_NOT_ENOUGH_ARGS,
118 });
119 return obj_err;
120 }
121 if (args->car == obj_nil) {
122 error_push((Error){
123 .type = ERR_TYPE_RUNTIME,
124 .value = ERR_NOT_ENOUGH_ARGS,
125 });
126 return obj_err;
127 }
128 Object *symbol = params->car;
129 Object *value = eval(env, args->car);
130 if (value == obj_err) {
131 return obj_err;
132 }
133 env_add_or_update_current(tmp, symbol, value);
134 args = args->cdr;
135 params = params->cdr;
136 }
137 if (args != obj_nil) {
138 error_push((Error){
139 .type = ERR_TYPE_RUNTIME,
140 .value = ERR_TOO_MANY_ARGS,
141 });
142 return obj_err;
143 }
144
145 // Copy temporary environment values to closure environment.
146 args = root->cdr;
147 params = lambda->params;
148 while (params != obj_nil) {
149 Object *symbol = params->car;
150 Object *value = env_lookup(tmp, symbol);
151 env_add_or_update_current(env, symbol, value);
152 args = args->cdr;
153 params = params->cdr;
154 }
155
156 // Release the temporary environment protection.
157 pop_active_env();
158
159 // Run the body of the function.
160 root = lambda->body;
161 while (root->cdr != obj_nil) {
162 if (eval(env, root->car) == obj_err) {
163 return obj_err;
164 };
165 root = root->cdr;
166 }
167 root = root->car;
168 goto eval_start;
169 } break;
170 }
171
172 error_push((Error){
173 .type = ERR_TYPE_RUNTIME,
174 .value = ERR_UNKNOWN_OBJ_TYPE,
175 });
176 return obj_err;
177
178eval_success:
179 if (recursion_active) {
180 // Remove stack protector.
181 pop_active_env();
182 }
183 return ret;
184}
185
186Object *
187proc_quote(Environment *env, Object *obj) {
188 (void)env;
189 return obj->car;
190}
191
192static inline Object *
193extract_car_with_type(Environment *env, Object *obj, ObjectType expected_type) {
194 if (obj == obj_nil) {
195 error_push((Error){
196 .type = ERR_TYPE_RUNTIME,
197 .value = ERR_NOT_ENOUGH_ARGS,
198 });
199 return obj_err;
200 }
201 Object *car = eval(env, obj->car);
202 if (car == obj_err) {
203 return obj_err;
204 }
205 if (car->type != expected_type) {
206 error_push((Error){
207 .type = ERR_TYPE_RUNTIME,
208 .value = ERR_WRONG_ARG_TYPE,
209 });
210 return obj_err;
211 }
212 return car;
213}
214
215//
216// Arithmetic procedures.
217//
218
219Object *
220proc_sum(Environment *env, Object *obj) {
221 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
222 obj = obj->cdr;
223 ssize_t tot = car->fixnum;
224 while (obj != obj_nil) {
225 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
226 tot += car->fixnum;
227 obj = obj->cdr;
228 }
229 return make_fixnum(tot);
230}
231
232Object *
233proc_sub(Environment *env, Object *obj) {
234 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
235 obj = obj->cdr;
236 ssize_t tot = car->fixnum;
237 while (obj != obj_nil) {
238 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
239 tot -= car->fixnum;
240 obj = obj->cdr;
241 }
242 return make_fixnum(tot);
243}
244
245Object *
246proc_mul(Environment *env, Object *obj) {
247 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
248 obj = obj->cdr;
249 ssize_t tot = car->fixnum;
250 while (obj != obj_nil) {
251 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
252 tot *= car->fixnum;
253 obj = obj->cdr;
254 }
255 return make_fixnum(tot);
256}
257
258Object *
259proc_div(Environment *env, Object *obj) {
260 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
261 obj = obj->cdr;
262 ssize_t tot = car->fixnum;
263 while (obj != obj_nil) {
264 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
265 if (car->fixnum == 0) {
266 error_push((Error){
267 .type = ERR_TYPE_RUNTIME,
268 .value = ERR_DIVISION_BY_ZERO,
269 });
270 return obj_err;
271 }
272 tot /= car->fixnum;
273 obj = obj->cdr;
274 }
275 return make_fixnum(tot);
276}
277
278Object *
279proc_mod(Environment *env, Object *obj) {
280 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
281 obj = obj->cdr;
282 ssize_t tot = car->fixnum;
283 while (obj != obj_nil) {
284 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
285 if (car->fixnum == 0) {
286 error_push((Error){
287 .type = ERR_TYPE_RUNTIME,
288 .value = ERR_DIVISION_BY_ZERO,
289 });
290 return obj_err;
291 }
292 tot %= car->fixnum;
293 obj = obj->cdr;
294 }
295 return make_fixnum(tot);
296}
297
298//
299// Display/Evaluation procedues.
300//
301
302Object *
303proc_display(Environment *env, Object *obj) {
304 display(eval(env, obj->car));
305 return obj_nil;
306}
307
308Object *
309proc_print(Environment *env, Object *obj) {
310 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_STRING);
311 StringView scanner = (StringView) {
312 .start = car->string,
313 .n = array_size(car->string),
314 };
315 while (scanner.n != 0) {
316 char c = sv_next(&scanner);
317 if (c == '\\' && sv_peek(&scanner) == 'n') {
318 putchar('\n');
319 sv_next(&scanner);
320 continue;
321 }
322 if (c == '\\' && sv_peek(&scanner) == '"') {
323 putchar('"');
324 sv_next(&scanner);
325 continue;
326 }
327 putchar(c);
328 }
329 return obj_nil;
330}
331
332Object *
333proc_newline(Environment *env, Object *obj) {
334 printf("\n");
335 (void)env;
336 (void)obj;
337 return obj_nil;
338}
339
340//
341// Type info procedures.
342//
343
344Object *
345proc_is_boolean(Environment *env, Object *obj) {
346 if (obj == obj_nil) {
347 error_push((Error){
348 .type = ERR_TYPE_RUNTIME,
349 .value = ERR_NOT_ENOUGH_ARGS,
350 });
351 return obj_err;
352 }
353 obj = eval(env, obj->car);
354 if (obj == obj_err) {
355 return obj_err;
356 }
357 return (obj == obj_true || obj == obj_false) ? obj_true : obj_false;
358}
359
360Object *
361proc_is_nil(Environment *env, Object *obj) {
362 if (obj == obj_nil) {
363 error_push((Error){
364 .type = ERR_TYPE_RUNTIME,
365 .value = ERR_NOT_ENOUGH_ARGS,
366 });
367 return obj_err;
368 }
369 obj = eval(env, obj->car);
370 if (obj == obj_err) {
371 return obj_err;
372 }
373 return obj == obj_nil ? obj_true : obj_false;
374}
375
376Object *
377proc_is_symbol(Environment *env, Object *obj) {
378 if (obj == obj_nil) {
379 error_push((Error){
380 .type = ERR_TYPE_RUNTIME,
381 .value = ERR_NOT_ENOUGH_ARGS,
382 });
383 return obj_err;
384 }
385 obj = eval(env, obj->car);
386 if (obj == obj_err) {
387 return obj_err;
388 }
389 return obj->type == OBJ_TYPE_SYMBOL ? obj_true : obj_false;
390}
391
392Object *
393proc_is_string(Environment *env, Object *obj) {
394 if (obj == obj_nil) {
395 error_push((Error){
396 .type = ERR_TYPE_RUNTIME,
397 .value = ERR_NOT_ENOUGH_ARGS,
398 });
399 return obj_err;
400 }
401 obj = eval(env, obj->car);
402 if (obj == obj_err) {
403 return obj_err;
404 }
405 return obj->type == OBJ_TYPE_STRING ? obj_true : obj_false;
406}
407
408Object *
409proc_is_fixnum(Environment *env, Object *obj) {
410 if (obj == obj_nil) {
411 error_push((Error){
412 .type = ERR_TYPE_RUNTIME,
413 .value = ERR_NOT_ENOUGH_ARGS,
414 });
415 return obj_err;
416 }
417 obj = eval(env, obj->car);
418 if (obj == obj_err) {
419 return obj_err;
420 }
421 return obj->type == OBJ_TYPE_FIXNUM ? obj_true : obj_false;
422}
423
424Object *
425proc_is_pair(Environment *env, Object *obj) {
426 if (obj == obj_nil) {
427 error_push((Error){
428 .type = ERR_TYPE_RUNTIME,
429 .value = ERR_NOT_ENOUGH_ARGS,
430 });
431 return obj_err;
432 }
433 obj = eval(env, obj->car);
434 if (obj == obj_err) {
435 return obj_err;
436 }
437 return obj->type == OBJ_TYPE_PAIR ? obj_true : obj_false;
438}
439
440Object *
441proc_is_procedure(Environment *env, Object *obj) {
442 if (obj == obj_nil) {
443 error_push((Error){
444 .type = ERR_TYPE_RUNTIME,
445 .value = ERR_NOT_ENOUGH_ARGS,
446 });
447 return obj_err;
448 }
449 obj = eval(env, obj->car);
450 if (obj == obj_err) {
451 return obj_err;
452 }
453 return obj->type == OBJ_TYPE_PROCEDURE ? obj_true : obj_false;
454}
455
456Object *
457proc_is_error(Environment *env, Object *obj) {
458 if (obj == obj_nil) {
459 error_push((Error){
460 .type = ERR_TYPE_RUNTIME,
461 .value = ERR_NOT_ENOUGH_ARGS,
462 });
463 return obj_err;
464 }
465 obj = eval(env, obj->car);
466 if (obj == obj_err) {
467 return obj_true;
468 }
469 return obj_false;
470}
471
472//
473// Boolean/conditional procedures.
474//
475
476Object *
477proc_not(Environment *env, Object *obj) {
478 if (obj == obj_nil) {
479 error_push((Error){
480 .type = ERR_TYPE_RUNTIME,
481 .value = ERR_NOT_ENOUGH_ARGS,
482 });
483 return obj_err;
484 }
485 obj = eval(env, obj->car);
486 if (obj == obj_err) {
487 return obj_err;
488 }
489 return obj == obj_false ? obj_true : obj_false;
490}
491
492Object *
493proc_and(Environment *env, Object *obj) {
494 while (obj != obj_nil) {
495 if (proc_not(env, obj) == obj_true) {
496 return obj_false;
497 }
498 obj = obj->cdr;
499 }
500 return obj_true;
501}
502
503Object *
504proc_or(Environment *env, Object *obj) {
505 while (obj != obj_nil) {
506 if (proc_not(env, obj) == obj_false) {
507 return obj_true;
508 }
509 obj = obj->cdr;
510 }
511 return obj_false;
512}
513
514Object *
515proc_cond(Environment *env, Object *obj) {
516 if (obj == obj_nil) {
517 error_push((Error){
518 .type = ERR_TYPE_RUNTIME,
519 .value = ERR_NOT_ENOUGH_ARGS,
520 });
521 return obj_err;
522 }
523 while (obj != obj_nil) {
524 Object *clause = obj->car;
525 if (clause->type != OBJ_TYPE_PAIR || clause->cdr == obj_nil) {
526 error_push((Error){
527 .type = ERR_TYPE_RUNTIME,
528 .value = ERR_WRONG_ARG_TYPE,
529 });
530 return obj_err;
531 }
532 Object *test = clause->car;
533 Object *value = clause->cdr->car;
534 Object *result = eval(env, test);
535 if (result == obj_err) {
536 return obj_err;
537 }
538 if (result == obj_true) {
539 return eval(env, value);
540 }
541 obj = obj->cdr;
542 }
543 return obj_nil;
544}
545
546Object *
547proc_num_less_than(Environment *env, Object *obj) {
548 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
549 obj = obj->cdr;
550 ssize_t prev = car->fixnum;
551 while (obj != obj_nil) {
552 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
553 if (prev >= car->fixnum) {
554 return obj_false;
555 }
556 prev = car->fixnum;
557 obj = obj->cdr;
558 }
559 return obj_true;
560}
561
562Object *
563proc_num_greater_than(Environment *env, Object *obj) {
564 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
565 obj = obj->cdr;
566 ssize_t prev = car->fixnum;
567 while (obj != obj_nil) {
568 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
569 if (prev <= car->fixnum) {
570 return obj_false;
571 }
572 prev = car->fixnum;
573 obj = obj->cdr;
574 }
575 return obj_true;
576}
577
578Object *
579proc_num_lesseq_than(Environment *env, Object *obj) {
580 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
581 obj = obj->cdr;
582 ssize_t prev = car->fixnum;
583 while (obj != obj_nil) {
584 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
585 if (prev > car->fixnum) {
586 return obj_false;
587 }
588 prev = car->fixnum;
589 obj = obj->cdr;
590 }
591 return obj_true;
592}
593
594Object *
595proc_num_greatereq_than(Environment *env, Object *obj) {
596 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
597 obj = obj->cdr;
598 ssize_t prev = car->fixnum;
599 while (obj != obj_nil) {
600 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
601 if (prev < car->fixnum) {
602 return obj_false;
603 }
604 prev = car->fixnum;
605 obj = obj->cdr;
606 }
607 return obj_true;
608}
609
610Object *
611proc_num_equal(Environment *env, Object *obj) {
612 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
613 obj = obj->cdr;
614 ssize_t prev = car->fixnum;
615 while (obj != obj_nil) {
616 car = extract_car_with_type(env, obj, OBJ_TYPE_FIXNUM);
617 if (prev != car->fixnum) {
618 return obj_false;
619 }
620 prev = car->fixnum;
621 obj = obj->cdr;
622 }
623 return obj_true;
624}
625
626//
627// List operation procedures.
628//
629
630Object *
631proc_car(Environment *env, Object *obj) {
632 if (obj == obj_nil) {
633 error_push((Error){
634 .type = ERR_TYPE_RUNTIME,
635 .value = ERR_NOT_ENOUGH_ARGS,
636 });
637 return obj_err;
638 }
639 obj = eval(env, obj->car);
640 if (obj == obj_err) {
641 return obj_err;
642 }
643 if (obj->type != OBJ_TYPE_PAIR) {
644 error_push((Error){
645 .type = ERR_TYPE_RUNTIME,
646 .value = ERR_WRONG_ARG_TYPE,
647 });
648 return obj_err;
649 }
650 return obj->car;
651}
652
653Object *
654proc_cdr(Environment *env, Object *obj) {
655 if (obj == obj_nil) {
656 error_push((Error){
657 .type = ERR_TYPE_RUNTIME,
658 .value = ERR_NOT_ENOUGH_ARGS,
659 });
660 return obj_err;
661 }
662 obj = eval(env, obj->car);
663 if (obj == obj_err) {
664 return obj_err;
665 }
666 if (obj->type != OBJ_TYPE_PAIR) {
667 error_push((Error){
668 .type = ERR_TYPE_RUNTIME,
669 .value = ERR_WRONG_ARG_TYPE,
670 });
671 return obj_err;
672 }
673 return obj->cdr;
674}
675
676Object *
677proc_cons(Environment *env, Object *obj) {
678 if (obj == obj_nil) {
679 error_push((Error){
680 .type = ERR_TYPE_RUNTIME,
681 .value = ERR_NOT_ENOUGH_ARGS,
682 });
683 return obj_err;
684 }
685 Object *head = make_pair(obj_nil, obj_nil);
686 push_root(head);
687 head->car = eval(env, obj->car);
688 if (head->car == obj_err) {
689 pop_root();
690 return obj_err;
691 }
692 head->cdr = eval(env, obj->cdr->car);
693 if (head->cdr == obj_err) {
694 pop_root();
695 return obj_err;
696 }
697 pop_root();
698 return head;
699}
700
701Object *
702proc_list(Environment *env, Object *obj) {
703 if (obj == obj_nil) {
704 return obj_nil;
705 }
706
707 Object *head = make_pair(obj_nil, obj_nil);
708 push_root(head);
709 Object *tmp = eval(env, obj->car);
710 if (tmp == obj_err) {
711 pop_root();
712 return obj_err;
713 }
714 head->car = tmp;
715 Object *curr = head;
716 obj = obj->cdr;
717 while (obj != obj_nil) {
718 tmp = eval(env, obj->car);
719 if (tmp == obj_err) {
720 pop_root();
721 return obj_err;
722 }
723 curr->cdr = make_pair(tmp, obj_nil);
724 curr = curr->cdr;
725 obj = obj->cdr;
726 }
727 pop_root();
728 return head;
729}
730
731//
732// Polymorphic procedures.
733//
734
735Object *
736proc_equal(Environment *env, Object *obj) {
737 if (obj == obj_nil || obj->cdr == obj_nil) {
738 error_push((Error){
739 .type = ERR_TYPE_RUNTIME,
740 .value = ERR_NOT_ENOUGH_ARGS,
741 });
742 return obj_err;
743 }
744 Object *a = eval(env, obj->car);
745 if (a == obj_err) {
746 return obj_err;
747 }
748 Object *b = eval(env, obj->cdr->car);
749 if (b == obj_err) {
750 return obj_err;
751 }
752 return obj_eq(a, b) ? obj_true : obj_false;
753}
754
755//
756// Variables and declarations.
757//
758
759Object *
760proc_define(Environment *env, Object *obj) {
761 if (obj == obj_nil || obj->cdr == obj_nil) {
762 error_push((Error){
763 .type = ERR_TYPE_RUNTIME,
764 .value = ERR_NOT_ENOUGH_ARGS,
765 });
766 return obj_err;
767 }
768
769 Object *symbol = obj->car;
770 if (symbol->type != OBJ_TYPE_SYMBOL) {
771 error_push((Error){
772 .type = ERR_TYPE_RUNTIME,
773 .value = ERR_WRONG_ARG_TYPE,
774 });
775 return obj_err;
776 }
777
778 Object *value = eval(env, obj->cdr->car);
779 if (value == obj_err) {
780 return obj_err;
781 }
782
783 env_add_or_update_current(env, symbol, value);
784 return obj_nil;
785}
786
787Object *
788proc_set(Environment *env, Object *obj) {
789 if (obj == obj_nil || obj->cdr == obj_nil) {
790 error_push((Error){
791 .type = ERR_TYPE_RUNTIME,
792 .value = ERR_NOT_ENOUGH_ARGS,
793 });
794 return obj_err;
795 }
796
797 Object *symbol = obj->car;
798 if (symbol->type != OBJ_TYPE_SYMBOL) {
799 error_push((Error){
800 .type = ERR_TYPE_RUNTIME,
801 .value = ERR_WRONG_ARG_TYPE,
802 });
803 return obj_err;
804 }
805
806 Object *value = eval(env, obj->cdr->car);
807 if (value == obj_err) {
808 return obj_err;
809 }
810
811 return env_update(env, symbol, value);
812}
813
814Object *
815proc_lambda(Environment *env, Object *obj) {
816 if (obj == obj_nil || obj->cdr == obj_nil) {
817 error_push((Error){
818 .type = ERR_TYPE_RUNTIME,
819 .value = ERR_NOT_ENOUGH_ARGS,
820 });
821 return obj_err;
822 }
823 Object *params = obj->car;
824 if (params != obj_nil && params->type != OBJ_TYPE_PAIR) {
825 error_push((Error){
826 .type = ERR_TYPE_RUNTIME,
827 .value = ERR_WRONG_ARG_TYPE,
828 });
829 return obj_err;
830 }
831 Object *body = obj->cdr;
832 Object *fun = alloc_object(OBJ_TYPE_LAMBDA);
833 fun->params = params;
834 fun->body = body;
835 fun->env = env;
836 return fun;
837}
838
839Object *
840proc_fun(Environment *env, Object *obj) {
841 if (obj == obj_nil || obj->cdr == obj_nil || obj->cdr->cdr == obj_nil) {
842 error_push((Error){
843 .type = ERR_TYPE_RUNTIME,
844 .value = ERR_NOT_ENOUGH_ARGS,
845 });
846 return obj_err;
847 }
848
849 Object *name = obj->car;
850 if (name->type != OBJ_TYPE_SYMBOL) {
851 error_push((Error){
852 .type = ERR_TYPE_RUNTIME,
853 .value = ERR_WRONG_ARG_TYPE,
854 });
855 return obj_err;
856 }
857
858 Object *params = obj->cdr->car;
859 if (params != obj_nil && params->type != OBJ_TYPE_PAIR) {
860 error_push((Error){
861 .type = ERR_TYPE_RUNTIME,
862 .value = ERR_WRONG_ARG_TYPE,
863 });
864 return obj_err;
865 }
866 Object *body = obj->cdr->cdr;
867 Object *fun = alloc_object(OBJ_TYPE_LAMBDA);
868 fun->params = params;
869 fun->body = body;
870 fun->env = env;
871 env_add_or_update_current(env, name, fun);
872 return obj_nil;
873}
874
875//
876// Evaluation.
877//
878
879Object *
880proc_eval(Environment *env, Object *obj) {
881 if (obj == obj_nil) {
882 error_push((Error){
883 .type = ERR_TYPE_RUNTIME,
884 .value = ERR_NOT_ENOUGH_ARGS,
885 });
886 return obj_err;
887 }
888 return eval(env, eval(env, obj->car));
889}
890
891//
892// Runtime configuration options.
893//
894
895Object *
896proc_supress_errors(Environment *env, Object *obj) {
897 Object *car = extract_car_with_type(env, obj, OBJ_TYPE_BOOL);
898 if (car == obj_err) {
899 return obj_err;
900 }
901
902 if (car == obj_true) {
903 supress_errors = true;
904 } else if (car == obj_false) {
905 supress_errors = false;
906 }
907 return obj_nil;
908}
909
910// TODO: map
911// TODO: apply
912// TODO: filter
913
914// TODO: fixnum left/right shift, mask, invert
915// TODO: add primitives for type transforms: string->symbol, symbol->string, etc
916// TODO: implement support for semi-quotes
917// TODO: LAMBDA
918// TODO: let
diff --git a/src/treewalk/primitives.h b/src/treewalk/primitives.h
deleted file mode 100644
index f874b17..0000000
--- a/src/treewalk/primitives.h
+++ /dev/null
@@ -1,60 +0,0 @@
1#ifndef BDL_PRIMITIVES_H
2#define BDL_PRIMITIVES_H
3
4// Function evaluation.
5Object * eval(Environment *env, Object *root);
6
7// Evaluation functions.
8Object * proc_quote(Environment *env, Object *obj);
9Object * proc_eval(Environment *env, Object *obj);
10
11// Arithmetic.
12Object * proc_sum(Environment *env, Object *obj);
13Object * proc_sub(Environment *env, Object *obj);
14Object * proc_mul(Environment *env, Object *obj);
15Object * proc_div(Environment *env, Object *obj);
16Object * proc_mod(Environment *env, Object *obj);
17
18// Printing.
19Object * proc_display(Environment *env, Object *obj);
20Object * proc_print(Environment *env, Object *obj);
21Object * proc_newline(Environment *env, Object *obj);
22
23// Type checking.
24Object * proc_is_boolean(Environment *env, Object *obj);
25Object * proc_is_nil(Environment *env, Object *obj);
26Object * proc_is_symbol(Environment *env, Object *obj);
27Object * proc_is_string(Environment *env, Object *obj);
28Object * proc_is_fixnum(Environment *env, Object *obj);
29Object * proc_is_pair(Environment *env, Object *obj);
30Object * proc_is_procedure(Environment *env, Object *obj);
31Object * proc_is_error(Environment *env, Object *obj);
32
33// Logical operations.
34Object * proc_not(Environment *env, Object *obj);
35Object * proc_and(Environment *env, Object *obj);
36Object * proc_or(Environment *env, Object *obj);
37Object * proc_cond(Environment *env, Object *obj);
38Object * proc_num_less_than(Environment *env, Object *obj);
39Object * proc_num_greater_than(Environment *env, Object *obj);
40Object * proc_num_lesseq_than(Environment *env, Object *obj);
41Object * proc_num_greatereq_than(Environment *env, Object *obj);
42Object * proc_num_equal(Environment *env, Object *obj);
43Object * proc_equal(Environment *env, Object *obj);
44
45// List operations.
46Object * proc_car(Environment *env, Object *obj);
47Object * proc_cdr(Environment *env, Object *obj);
48Object * proc_cons(Environment *env, Object *obj);
49Object * proc_list(Environment *env, Object *obj);
50
51// Environment/variable manipulation.
52Object * proc_define(Environment *env, Object *obj);
53Object * proc_set(Environment *env, Object *obj);
54Object * proc_lambda(Environment *env, Object *obj);
55Object * proc_fun(Environment *env, Object *obj);
56
57// Runtinme configuration.
58Object * proc_supress_errors(Environment *env, Object *obj);
59
60#endif // BDL_PRIMITIVES_H
diff --git a/src/treewalk/read_line.c b/src/treewalk/read_line.c
deleted file mode 100644
index 03146ad..0000000
--- a/src/treewalk/read_line.c
+++ /dev/null
@@ -1,32 +0,0 @@
1#include "read_line.h"
2
3static char readline_buf[RL_BUF_SIZE];
4
5StringView
6read_line(void) {
7 // Clear buffer.
8 for (size_t i = 0; i < RL_BUF_SIZE; i++) {
9 readline_buf[i] = 0;
10 }
11
12 // Barebones readline implementation.
13 size_t n = 0;
14 char c;
15 while ((c = getchar()) != '\n') {
16 if (c == '\b') {
17 readline_buf[n] = '\0';
18 n--;
19 } else if (c == EOF || c == '\0') {
20 return (StringView){ .start = NULL, .n = 0 };
21 } else if ((c >= ' ' && c <= '~') && n < RL_BUF_SIZE) {
22 readline_buf[n] = c;
23 n++;
24 }
25 }
26
27 StringView sv = (StringView){
28 .start = (char *)&readline_buf,
29 .n = n,
30 };
31 return sv;
32}
diff --git a/src/treewalk/read_line.h b/src/treewalk/read_line.h
deleted file mode 100644
index 160bce0..0000000
--- a/src/treewalk/read_line.h
+++ /dev/null
@@ -1,10 +0,0 @@
1#ifndef BDL_READ_LINE_H
2#define BDL_READ_LINE_H
3
4#include "string_view.h"
5
6StringView read_line(void);
7
8#define RL_BUF_SIZE 1024
9
10#endif // BDL_READ_LINE_H
diff --git a/src/treewalk/singletons.c b/src/treewalk/singletons.c
deleted file mode 100644
index eb9c397..0000000
--- a/src/treewalk/singletons.c
+++ /dev/null
@@ -1,17 +0,0 @@
1#include "environment.h"
2#include "gc.h"
3#include "objects.h"
4
5// Global garbage collector singleton.
6static GC gc;
7
8// Special singleton Objects.
9static Object *obj_nil;
10static Object *obj_true;
11static Object *obj_false;
12static Object *obj_err;
13static Object *obj_quote;
14static Object *proc_if;
15
16// Global environment.
17static Environment *global_env;
diff --git a/src/treewalk/string_view.c b/src/treewalk/string_view.c
deleted file mode 100644
index 39fabe9..0000000
--- a/src/treewalk/string_view.c
+++ /dev/null
@@ -1,40 +0,0 @@
1#include "string_view.h"
2
3char
4sv_next(StringView *sv) {
5 if (sv->n == 0) {
6 return '\0';
7 }
8 char c = sv->start[0];
9 sv->start++;
10 sv->n--;
11 return c;
12}
13
14char
15sv_peek(const StringView *sv) {
16 if (sv->n == 0) {
17 return '\0';
18 }
19 return sv->start[0];
20}
21
22bool
23sv_equal(const StringView *a, const StringView *b) {
24 if (a->n != b->n) {
25 return false;
26 }
27 for (size_t i = 0; i < a->n; i++) {
28 if (a->start[i] != b->start[i]) {
29 return false;
30 }
31 }
32 return true;
33}
34
35void
36sv_write(const StringView *sv, FILE *file) {
37 for (size_t i = 0; i < sv->n; i++) {
38 putc(sv->start[i], file);
39 }
40}
diff --git a/src/treewalk/string_view.h b/src/treewalk/string_view.h
deleted file mode 100644
index 42273ab..0000000
--- a/src/treewalk/string_view.h
+++ /dev/null
@@ -1,21 +0,0 @@
1#ifndef BDL_STRINGVIEW_H
2#define BDL_STRINGVIEW_H
3
4typedef struct StringView {
5 char *start;
6 size_t n;
7} StringView;
8
9// Consume a character in the stream.
10char sv_next(StringView *sv);
11
12// Check what is the current character in the stream.
13char sv_peek(const StringView *sv);
14
15// Compare if the arguments are the same.
16bool sv_equal(const StringView *a, const StringView *b);
17
18// Write a character to the given output stream.
19void sv_write(const StringView *sv, FILE *file);
20
21#endif // BDL_STRINGVIEW_H
diff --git a/src/x86_64/postlude.asm b/src/x86_64/postlude.asm
deleted file mode 100644
index 45be7ee..0000000
--- a/src/x86_64/postlude.asm
+++ /dev/null
@@ -1,12 +0,0 @@
1
2_start_return:
3 ;; return the last value in the stack
4 pop rdi
5 call display
6
7exit:
8 ;; exit syscall
9 mov rax, 60
10 xor rdi, rdi
11 syscall
12
diff --git a/src/x86_64/prelude.asm b/src/x86_64/prelude.asm
deleted file mode 100644
index 81a2633..0000000
--- a/src/x86_64/prelude.asm
+++ /dev/null
@@ -1,134 +0,0 @@
1section .text
2printdln:
3 sar rdi, FIXNUM_SHIFT
4 sub rsp, 40
5 mov BYTE [rsp+31], 10
6 test rdi, rdi
7 jne .L2
8 mov BYTE [rsp+30], 48
9 mov eax, 30
10 mov r8d, 2
11.L3:
12 lea rsi, [rsp+rax]
13 mov rdx, r8
14 mov rdi, 1
15 mov rax, 1
16 syscall
17 add rsp, 40
18 ret
19.L2:
20 mov r10d, 1
21 js .L12
22.L4:
23 mov r8d, 1
24 lea r9, [rsp+31]
25 mov rsi, -3689348814741910323
26.L5:
27 mov rax, rdi
28 mov rcx, r9
29 mul rsi
30 sub rcx, r8
31 shr rdx, 3
32 lea rax, [rdx+rdx*4]
33 add rax, rax
34 sub rdi, rax
35 mov rax, r8
36 add r8, 1
37 add edi, 48
38 mov BYTE [rcx], dil
39 mov rdi, rdx
40 test rdx, rdx
41 jne .L5
42 cmp r10d, -1
43 jne .L10
44 not r8
45 mov BYTE [rsp+32+r8], 45
46 lea r8, [rax+2]
47.L10:
48 mov eax, 32
49 sub rax, r8
50 jmp .L3
51.L12:
52 neg rdi
53 mov r10d, -1
54 jmp .L4
55 ret
56
57printbool:
58 shr rdi, BOOL_SHIFT
59 cmp rdi, 0
60 je print_false
61 mov rsi, true_str ; addr
62 mov rdx, 5 ; number of bytes
63 jmp bool_write
64print_false:
65 mov rsi, false_str ; addr
66 mov rdx, 6 ; number of bytes
67
68bool_write:
69 mov rax, 1
70 mov rdi, 1
71 syscall
72 ret
73
74printstring:
75 mov rsi, rdi
76 mov rax, PTR_MASK
77 and rsi, rax
78 mov rdx, [rsi]
79 add rsi, 8
80 mov rax, 1
81 mov rdi, 1
82 syscall
83 ret
84
85printlambda:
86 mov rsi, lambda_str
87 mov rdx, [rsi]
88 add rsi, 8
89 mov rax, 1
90 mov rdi, 1
91 syscall
92 ret
93
94display:
95 ;; is nil?
96 mov rax, rdi
97 cmp rax, NIL_VAL
98 je display_end
99
100 ;; is boolean?
101 mov rax, rdi
102 and rax, BOOL_MASK
103 cmp rax, BOOL_TAG
104 jne not_bool
105 call printbool
106 ret
107not_bool:
108
109 ;; is string?
110 mov rax, rdi
111 and rax, STRING_MASK
112 cmp rax, STRING_TAG
113 jne not_string
114 call printstring
115 ret
116not_string:
117
118 ;; is lambda?
119 mov rax, rdi
120 and rax, LAMBDA_MASK
121 cmp rax, LAMBDA_TAG
122 jne not_lambda
123 call printlambda
124 ret
125not_lambda:
126
127 ;; is fixnum?
128 mov rax, rdi
129 and rax, FIXNUM_MASK
130 cmp rax, FIXNUM_TAG
131 jne display_end
132 call printdln
133display_end:
134 ret
generated by cgit v1.2.1 (git 2.18.0) at 2024-05-02 01:02:10 +0000