aboutsummaryrefslogtreecommitdiffstats
path: root/src/bootstrap/main.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/bootstrap/main.c')
-rwxr-xr-xsrc/bootstrap/main.c674
1 files changed, 7 insertions, 667 deletions
diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c
index f5653d6..419ce91 100755
--- a/src/bootstrap/main.c
+++ b/src/bootstrap/main.c
@@ -5,644 +5,20 @@
5#include <string.h> 5#include <string.h>
6 6
7#include "shorthand.h" 7#include "shorthand.h"
8 8#include "string_view.c"
9#include "readline.c"
10#include "lexer.c"
11#include "objects.c"
12#include "parser.c"
13#include "environment.c"
14#include "primitives.c"
9 15
10// FIXME: We are not worried right now about freeing memory, but we should in 16// FIXME: We are not worried right now about freeing memory, but we should in
11// the future. 17// the future.
12// TODO: Better error messages. 18// TODO: Better error messages.
13 19
14typedef struct StringView {
15 char *start;
16 size_t n;
17} StringView;
18
19void
20sv_write(StringView sv) {
21 for (size_t i = 0; i < sv.n; i++) {
22 putchar(sv.start[i]);
23 }
24}
25
26bool
27sv_equal(StringView a, StringView b) {
28 if (a.n == b.n) {
29 for (size_t i = 0; i < a.n; i++) {
30 if (a.start[i] != b.start[i]) {
31 return false;
32 }
33 }
34 return true;
35 }
36 return false;
37}
38
39#define READLINE_VALID_CHAR(C) (((u8)(C) >= 0x20 && (u8)(C) < 0x7F) || (C) == '\n')
40
41StringView
42read_line(FILE *fd, char delimiter) {
43 #define RL_BUF_SIZE 1024
44 static char readline_buf[RL_BUF_SIZE];
45
46 // Clear buffer.
47 for (size_t i = 0; i < RL_BUF_SIZE; i++) {
48 readline_buf[i] = 0;
49 }
50
51 // Barebones readline implementation.
52 size_t n = 0;
53 char c;
54 while ((c = getc(fd)) != delimiter) {
55 if (c == '\b') {
56 readline_buf[n] = '\0';
57 n--;
58 } else if (READLINE_VALID_CHAR(c) && n < RL_BUF_SIZE) {
59 readline_buf[n] = c;
60 n++;
61 }
62 }
63
64 return (StringView){.start = (char *)&readline_buf, .n = n};
65}
66
67typedef enum TokenType {
68 TOKEN_UNKNOWN = 0,
69 TOKEN_LPAREN,
70 TOKEN_RPAREN,
71 TOKEN_FIXNUM,
72 TOKEN_SYMBOL,
73 TOKEN_BOOL,
74 TOKEN_STRING,
75} TokenType;
76
77typedef struct Token {
78 TokenType type;
79 StringView value;
80} Token;
81
82typedef struct Tokens {
83 Token *start;
84 size_t n;
85} Tokens;
86
87#define TRUE_TOKEN (StringView){"true", 4}
88#define FALSE_TOKEN (StringView){"false", 5}
89#define LPAREN_TOKEN (StringView){"(", 1}
90#define RPAREN_TOKEN (StringView){")", 1}
91
92TokenType
93find_token_type(StringView value) {
94 bool is_fixnum = true;
95 for (size_t i = 0; i < value.n; i++) {
96 char c = value.start[i];
97 if (i == 0 && c == '-' && value.n > 1) {
98 continue;
99 }
100 if (!isdigit(c)) {
101 is_fixnum = false;
102 break;
103 }
104 }
105 if (is_fixnum) {
106 return TOKEN_FIXNUM;
107 }
108
109 if (sv_equal(value, TRUE_TOKEN) || sv_equal(value, FALSE_TOKEN)) {
110 return TOKEN_BOOL;
111 }
112
113 return TOKEN_SYMBOL;
114}
115
116Tokens
117tokenize(StringView sv) {
118 // NOTE: Not allocating any memory for now, but we are limited by a maximum
119 // number of tokens we can process.
120 #define TOKENS_BUF_SIZE 1024
121 static Token tokens_buf[TOKENS_BUF_SIZE];
122
123 // Clear buffer.
124 for (size_t i = 0; i < TOKENS_BUF_SIZE; i++) {
125 tokens_buf[i] = (Token){0};
126 }
127
128 size_t n = 0;
129 size_t token_n = 0;
130 for (size_t i = 0; i < sv.n; i++) {
131 switch (sv.start[i]) {
132 case ' ':
133 case '\f':
134 case '\n':
135 case '\r':
136 case '\t':
137 case '\v': {
138 if (token_n != 0) {
139 Token token = (Token){
140 .type = TOKEN_UNKNOWN,
141 .value = (StringView){
142 .start = &sv.start[i - token_n],
143 .n = token_n,
144 }
145 };
146 token.type = find_token_type(token.value);
147 tokens_buf[n++] = token;
148 token_n = 0;
149 }
150 } break;
151 case ';': {
152 if (token_n != 0) {
153 Token token = (Token){
154 .type = TOKEN_UNKNOWN,
155 .value = (StringView){
156 .start = &sv.start[i - token_n],
157 .n = token_n,
158 }
159 };
160 token.type = find_token_type(token.value);
161 tokens_buf[n++] = token;
162 token_n = 0;
163 }
164
165 // Advance until the next newline.
166 do {
167 i++;
168 } while (i < sv.n && sv.start[(i + 1)] != '\n');
169 } break;
170 case '"': {
171 if (token_n != 0) {
172 fprintf(stderr, "error: string started inside symbol\n");
173 return (Tokens){0};
174 }
175
176 // Find end delimiter.
177 size_t string_start = i + 1;
178 size_t string_end = i + 1;
179 while (true) {
180 if (sv.start[string_end] == '"' && sv.start[string_end - 1] != '\\') {
181 break;
182 }
183 if (string_end >= sv.n) {
184 fprintf(stderr, "error: string delimiter not found\n");
185 return (Tokens){0};
186 }
187 string_end++;
188 }
189
190 Token token = (Token){
191 .type = TOKEN_STRING,
192 .value = (StringView){
193 .start = &sv.start[string_start],
194 .n = string_end - string_start,
195 }
196 };
197 tokens_buf[n++] = token;
198 token_n = 0;
199 i += string_end - string_start + 1;
200 } break;
201 case '(': {
202 if ((i + 1) < sv.n) {
203 char next_c = sv.start[i + 1];
204 if (isspace(next_c)) {
205 fprintf(stderr, "error: lparen delimiter followed by space\n");
206 return (Tokens){0};
207 }
208 }
209
210 if (token_n != 0) {
211 fprintf(stderr, "error: lparen delimiter within symbol name\n");
212 return (Tokens){0};
213 }
214
215 Token token = (Token){
216 .type = TOKEN_LPAREN,
217 .value = LPAREN_TOKEN,
218 };
219 tokens_buf[n++] = token;
220 } break;
221 case ')': {
222 if ((i + 1) < sv.n) {
223 char next_c = sv.start[i + 1];
224 if ((next_c != ')' && !isspace(next_c))) {
225 fprintf(stderr, "error: rparen delimiter within symbol name\n");
226 return (Tokens){0};
227 }
228 }
229
230 if (token_n != 0) {
231 // Push previous token.
232 Token token = (Token){
233 .type = TOKEN_UNKNOWN,
234 .value = (StringView){
235 .start = &sv.start[i - token_n],
236 .n = token_n,
237 }
238 };
239 token.type = find_token_type(token.value);
240 tokens_buf[n++] = token;
241 token_n = 0;
242 }
243
244 Token token = (Token){
245 .type = TOKEN_RPAREN,
246 .value = RPAREN_TOKEN,
247 };
248 tokens_buf[n++] = token;
249 } break;
250 case EOF: {
251 break;
252 } break;
253 default: {
254 token_n++;
255 } break;
256 }
257 }
258 if (token_n != 0) {
259 // End of line encountered.
260 Token token = (Token){
261 .type = TOKEN_UNKNOWN,
262 .value = (StringView){
263 .start = &sv.start[sv.n - token_n],
264 .n = token_n,
265 }
266 };
267 token.type = find_token_type(token.value);
268 tokens_buf[n++] = token;
269 }
270
271 return (Tokens){.start = (Token *)&tokens_buf, .n = n};
272}
273
274Token *
275consume_token(Tokens *tokens) {
276 if (tokens->n == 0) {
277 return NULL;
278 }
279 Token *ret = tokens->start;
280 tokens->start = &tokens->start[1];
281 tokens->n--;
282 return ret;
283}
284
285typedef enum ObjectType {
286 OBJ_TYPE_FIXNUM,
287 OBJ_TYPE_BOOL,
288 OBJ_TYPE_NIL,
289 OBJ_TYPE_SYMBOL,
290 OBJ_TYPE_STRING,
291 OBJ_TYPE_PAIR,
292 OBJ_TYPE_PROCEDURE,
293} ObjectType;
294
295typedef struct Object {
296 ObjectType type;
297 union {
298 // OBJ_TYPE_FIXNUM
299 ssize_t fixnum;
300
301 // OBJ_TYPE_BOOL
302 bool boolean;
303
304 // OBJ_TYPE_STRING
305 struct {
306 char *string;
307 size_t string_n;
308 };
309
310 // OBJ_TYPE_PAIR
311 struct {
312 struct Object *car;
313 struct Object *cdr;
314 };
315
316 // OBJ_TYPE_SYMBOL
317 struct {
318 char *symbol;
319 size_t symbol_n;
320 };
321
322 // OBJ_TYPE_PROCEDURE
323 struct Object *(*proc)(struct Object *args);
324 };
325} Object;
326
327//
328// Singletons.
329//
330
331Object *obj_nil;
332Object *obj_true;
333Object *obj_false;
334
335//
336// Environment.
337//
338
339typedef struct EnvSymbol {
340 Object *symbol;
341 Object *value;
342} EnvSymbol;
343
344#define ENV_SIZE 256
345static EnvSymbol environment[ENV_SIZE];
346static size_t env_n = 0;
347
348Object *
349make_fixnum(ssize_t num) {
350 Object *obj = malloc(sizeof(Object));
351 obj->type = OBJ_TYPE_FIXNUM;
352 obj->fixnum = num;
353 return obj;
354}
355
356Object *
357make_boolean(bool b) {
358 Object *obj = malloc(sizeof(Object));
359 obj->type = OBJ_TYPE_BOOL;
360 obj->boolean = b;
361 return obj;
362}
363
364Object *
365make_empty_string(void) {
366 Object *obj = malloc(sizeof(Object));
367 obj->type = OBJ_TYPE_STRING;
368 obj->string = NULL;
369 obj->string_n = 0;
370 return obj;
371}
372
373void
374append_string(Object *string, StringView sv) {
375 assert(string != NULL);
376 assert(string->type == OBJ_TYPE_STRING);
377
378 if (sv.n == 0) {
379 return;
380 }
381
382 string->string = realloc(string->string, (string->string_n + sv.n) * sizeof(char));
383 memcpy(string->string + string->string_n, sv.start, sv.n);
384 string->string_n += sv.n;
385}
386
387Object *
388make_symbol(const char *str, size_t n) {
389 Object *obj = malloc(sizeof(Object));
390 obj->type = OBJ_TYPE_SYMBOL;
391 obj->string = malloc(sizeof(char) * n);
392 memcpy(obj->string, str, n);
393 obj->string_n = n;
394 return obj;
395}
396
397Object *
398make_empty_list(void) {
399 Object *obj = malloc(sizeof(Object));
400 obj->type = OBJ_TYPE_NIL;
401 return obj;
402}
403
404Object *
405make_procedure(Object *(*proc)(struct Object *args)) {
406 Object *obj = malloc(sizeof(Object));
407 obj->type = OBJ_TYPE_PROCEDURE;
408 obj->proc = proc;
409 return obj;
410}
411
412Object *
413make_pair(Object *car, Object *cdr) {
414 Object *obj = malloc(sizeof(Object));
415 obj->type = OBJ_TYPE_PAIR;
416 obj->car = car;
417 obj->cdr = cdr;
418 return obj;
419}
420
421Object *
422parse(Tokens *tokens) {
423 while (tokens->n > 0) {
424 Token *token = consume_token(tokens);
425 if (token == NULL) {
426 return NULL;
427 }
428
429 switch (token->type) {
430 case TOKEN_FIXNUM: {
431 ssize_t num = 0;
432 int sign = 1;
433 for (size_t i = 0; i < token->value.n; i++) {
434 char c = token->value.start[i];
435 if (c == '-') {
436 sign = -1;
437 continue;
438 }
439 num = num * 10 + (c - '0');
440 }
441 return make_fixnum(num * sign);
442 } break;
443 case TOKEN_BOOL: {
444 if (sv_equal(token->value, TRUE_TOKEN)) {
445 return obj_true;
446 }
447 if (sv_equal(token->value, FALSE_TOKEN)) {
448 return obj_false;
449 }
450 } break;
451 case TOKEN_RPAREN: {
452 return NULL;
453 } break;
454 case TOKEN_LPAREN: {
455 if (tokens->n > 0 && tokens->start[0].type == TOKEN_RPAREN) {
456 return obj_nil;
457 }
458
459 Object *next_obj = parse(tokens);
460 if (next_obj == NULL) {
461 return NULL;
462 }
463 Object *root = make_pair(next_obj, obj_nil);
464 Object *list = root;
465 while (tokens->n > 0 && (next_obj = parse(tokens)) != NULL) {
466 list->cdr = make_pair(next_obj, obj_nil);
467 list = list->cdr;
468 }
469 return root;
470 } break;
471 case TOKEN_STRING: {
472 Object *obj = make_empty_string();
473 append_string(obj, token->value);
474 return obj;
475 } break;
476 case TOKEN_SYMBOL: {
477 return make_symbol(token->value.start, token->value.n);
478 } break;
479 default: {
480 fprintf(stderr, "error: unknown token\n");
481 } break;
482 }
483 }
484
485 return NULL;
486}
487
488void display(Object *root);
489
490void
491display_pair(Object *root) {
492 display(root->car);
493 if (root->cdr->type == OBJ_TYPE_PAIR) {
494 printf(" ");
495 display_pair(root->cdr);
496 } else if (root->cdr->type == OBJ_TYPE_NIL) {
497 return;
498 } else {
499 printf(" . ");
500 display(root->cdr);
501 }
502}
503
504void
505display(Object *root) {
506 if (root == NULL) {
507 return;
508 }
509
510 switch (root->type) {
511 case OBJ_TYPE_FIXNUM: {
512 printf("%zd", root->fixnum);
513 } break;
514 case OBJ_TYPE_BOOL: {
515 if (root->boolean) {
516 printf("true");
517 } else {
518 printf("false");
519 }
520 } break;
521 case OBJ_TYPE_NIL: {
522 printf("()");
523 } break;
524 case OBJ_TYPE_STRING: {
525 printf("\"%.*s\"", (int)root->string_n, root->string);
526 } break;
527 case OBJ_TYPE_SYMBOL: {
528 printf(":%.*s", (int)root->symbol_n, root->symbol);
529 } break;
530 case OBJ_TYPE_PAIR: {
531 printf("(");
532 display_pair(root);
533 printf(")");
534 } break;
535 default: {
536 printf("TYPE NOT IMPLEMENTED FOR DISPLAY.");
537 } break;
538 }
539}
540
541#define REPL_PROMPT "bdl> " 20#define REPL_PROMPT "bdl> "
542 21
543Object * eval(Object *root);
544
545Object *
546proc_add(Object *args) {
547 ssize_t tot = 0;
548 while (args->type == OBJ_TYPE_PAIR) {
549 Object *car = eval(args->car);
550 if (car->type != OBJ_TYPE_FIXNUM) {
551 fprintf(stderr, "addition not supported for type %d\n", car->type);
552 return NULL;
553 }
554 tot += car->fixnum;
555 args = args->cdr;
556 }
557 return make_fixnum(tot);
558}
559
560Object *
561proc_sub(Object *args) {
562 if (args->type != OBJ_TYPE_PAIR) {
563 fprintf(stderr, "substraction not supported for type %d\n", args->type);
564 return NULL;
565 }
566
567 // Extract first parameter.
568 Object *car = eval(args->car);
569 args = args->cdr;
570 ssize_t tot = car->fixnum;
571
572 while (args->type == OBJ_TYPE_PAIR) {
573 Object *car = eval(args->car);
574 if (car->type != OBJ_TYPE_FIXNUM) {
575 fprintf(stderr, "substraction not supported for type %d\n", car->type);
576 return NULL;
577 }
578 tot -= car->fixnum;
579 args = args->cdr;
580 }
581 return make_fixnum(tot);
582}
583
584Object *
585proc_mul(Object *args) {
586 ssize_t tot = 1;
587 while (args->type == OBJ_TYPE_PAIR) {
588 Object *car = eval(args->car);
589 if (car->type != OBJ_TYPE_FIXNUM) {
590 fprintf(stderr, "multiply not supported for type %d\n", car->type);
591 return NULL;
592 }
593 tot *= car->fixnum;
594 args = args->cdr;
595 }
596 return make_fixnum(tot);
597}
598
599Object *
600proc_div(Object *args) {
601 if (args->type != OBJ_TYPE_PAIR) {
602 fprintf(stderr, "substraction not supported for type %d\n", args->type);
603 return NULL;
604 }
605
606 // Extract first parameter.
607 Object *car = eval(args->car);
608 args = args->cdr;
609 ssize_t tot = car->fixnum;
610
611 while (args->type == OBJ_TYPE_PAIR) {
612 Object *car = eval(args->car);
613 if (car->type != OBJ_TYPE_FIXNUM) {
614 fprintf(stderr, "div not supported for type %d\n", car->type);
615 return NULL;
616 }
617 tot /= car->fixnum;
618 args = args->cdr;
619 }
620 return make_fixnum(tot);
621}
622
623bool
624symbol_eq(Object *a, Object *b) {
625 if (a->type != b->type || a->type != OBJ_TYPE_SYMBOL || a->symbol_n != b->symbol_n) {
626 return false;
627 }
628 for (size_t i = 0; i < a->symbol_n; i++) {
629 if (a->symbol[i] != b->symbol[i]) {
630 return false;
631 }
632 }
633 return true;
634}
635
636Object *
637find_environment_symbol(Object *symbol) {
638 for (size_t i = 0; i < env_n; i++) {
639 if (symbol_eq(environment[i].symbol, symbol)) {
640 return environment[i].value;
641 }
642 }
643 return NULL;
644}
645
646void 22void
647init(void) { 23init(void) {
648 // Clear env. 24 // Clear env.
@@ -662,42 +38,6 @@ init(void) {
662 environment[env_n++] = (EnvSymbol){make_symbol("/", 1), make_procedure(proc_div)}; 38 environment[env_n++] = (EnvSymbol){make_symbol("/", 1), make_procedure(proc_div)};
663} 39}
664 40
665Object *
666eval(Object *root) {
667 if (root == NULL) {
668 return NULL;
669 }
670
671 switch (root->type) {
672 case OBJ_TYPE_FIXNUM:
673 case OBJ_TYPE_BOOL:
674 case OBJ_TYPE_NIL:
675 case OBJ_TYPE_STRING:
676 case OBJ_TYPE_SYMBOL: {
677 return root;
678 } break;
679 case OBJ_TYPE_PAIR: {
680 if (root->car->type == OBJ_TYPE_SYMBOL) {
681 Object *value = find_environment_symbol(root->car);
682 if (value == NULL) {
683 printf("error: symbol not found: `");
684 display(root->car);
685 printf("`\n");
686 return NULL;
687 }
688 if (value->type == OBJ_TYPE_PROCEDURE) {
689 return value->proc(root->cdr);
690 }
691 }
692 } break;
693 default: {
694 printf("error: can't eval type %d.\n", root->type);
695 } break;
696 }
697
698 return NULL;
699}
700
701void 41void
702eval_line(FILE *fd, char delimiter) { 42eval_line(FILE *fd, char delimiter) {
703 StringView line = read_line(fd, delimiter); 43 StringView line = read_line(fd, delimiter);
generated by cgit v1.2.1 (git 2.18.0) at 2024-05-18 05:02:05 +0000